# Backtracking Recursion

Optional Node

Backtracking is a general algorithm for solving problems by searching through all possible cases until a solution is found. This search is done with recursion.

### Correct Change Challenge

Correct Change asked if you could reach a certain sum with pennies and nickels. However, in Zumbania, the coins can be worth any amount from 0 to 50 Zumbanian cents. This makes it difficult to know if you have the right change to pay for something, so you've been asked to write a program that will determine this.

The Zumbanian 37-cent piece, from Wikipedia

You will be given a list of numbers where the first number is the desired sum and the remaining numbers are the coins. Determine if the coins can be added together to reach the exact sum. You cannot use the same coin twice, but you can use duplicate coins (if there are any).

For example, when given `{12, 1, 2, 3, 4, 5}`, print `true` since 1+2+4+5 = 12 (among other possibilities). When given `{11, 1, 5, 9, 13}`, print `false`, since there's no way to reach a sum of `11` with those numbers.

### Finding an Algorithm

Can you write instructions in english for a computer to solve this problem? You don't need a "smart" algorithm that figures out a shortcut to the answer; the computer can just try out every possible selection of coins until it either reaches the sum or determines that it's impossible. But the computer needs to know precisely how to try out every possibility. See if you can formulate a way, then click below.

### Converting it to code

The algorithm described above could not be encoded with a simple loop. This is because it "splits in two" each time to try out every possibility, while a loop just goes through things in order. See if you can describe a recursive function that solves this problem, before clicking below.

You've seen a description of the algorithm and code, now see if you can write the code to solve the challenge!

### Challenge

Given a number `k` and a list of coins `ar`, determine if the coins can be added together to equal `k`. Print `true` if you can get the exact sum and `false` otherwise.

(The boilerplate code passes in 2 variables: the list of numbers `ar` and the desired sum `k`.)

Alternatively, you can try out Learneroo before signing up.

• #### greg

Any answers or help for this one? I find the backtracking code suggestion pretty vague... Thanks!

• #### Learneroo

See if the new hint help.

• #### greg

Thanks! Much clearer.
Greg

• #### jasson harsojo

static boolean groupSum(int index, int[] nums, int sum) {
//base case: check if reached sum
if(index==nums.length-1){
if(sum==0)return true;