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.

Try Out Every Possibility
Go through the array of coins in order. For each coin you reach, you can either add it your sum, or ignore it. Try each of these possibilities, and go on to the next coin within each one of them. Then repeat the same process with the next coin.

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.

Backtracking Code
Instead of a loop, create a recursive function that takes in the desired number and the remaining array separately, while keeping track of an index location in the array.

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!

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.
[null, {"document_url": "https://www.learneroo.com/modules/71/nodes/400", "unformatted_src": "https://s3.amazonaws.com/learneroo-images/main/weird-coin.png", "src": "https://s3.amazonaws.com/learneroo-images/main/weird-coin.png", "formatted_filename": "weird coin", "alt_text": "Zumbanian 37-cent piece"}, null]