Backtracking Recursion

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!