Backtracking Recursion
Optional NodeBacktracking 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
jasson harsojo
Nov 10, 10:23 PMstatic boolean groupSum(int index, int[] nums, int sum) {
//base case: check if reached sum
if(index==nums.length-1){
if(sum==0)return true;
my code doesn't work out :(
anyone can help?
still bit confuse with recursion