# 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.

The function should go through the array one number at a time, and recursively call itself twice: Once, with the coin subtracted from the desired sum, and once without the coin. The beginning if the function should check if the end of the array has been reached, and check if the sum is down to 0 or not.

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`

.)

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

## Comments

## greg

Jan 26, 3:04 AMAny answers or help for this one? I find the backtracking code suggestion pretty vague... Thanks!

## Learneroo

Jan 26, 7:57 AMSee if the new hint help.

## greg

Jan 27, 12:08 AMThanks! Much clearer.

Greg