# Need help with Java recursion problem!

• June 5th, 2012, 06:53 AM
eyesackery
Need help with Java recursion problem!
Hey guys, have been struggling with a recursion homework problem. Would be very appreciative if someone could give me a nudge in the right direction, or a hint. :)

The Question (The algorithm has to use recursion, no loops allowed.

////////////////////////////// PROBLEM STATEMENT //////////////////////////////
// Given an array of ints, is it possible to choose a group of some of the
// ints, such that the group sums to the given target with this additional
// constraint: If a value in the array is chosen to be in the group, the
// value immediately following it in the array must not be chosen. (No loops
// needed.)
// (0, {2, 5, 10, 4}, 12) -> true
// (0, {2, 5, 10, 4}, 14) -> false
// (0, {2, 5, 10, 4}, 7) -> false
//////////////////////////////////////////////////////////////////////////////////////

Thanks guys, got some really helpful feedback last night I posted a thread! :)
• June 5th, 2012, 07:11 AM
KevinWorkman
Re: Need help with Java recursion problem!
What have you tried? Where are you stuck? What part of this confuses you?

Recommended reading: Starting Writing a Program
• June 5th, 2012, 08:12 AM
eyesackery
Re: Need help with Java recursion problem!
Recursion on the whole has been difficult to understand, but I have been getting through a few easier problems and gaining understanding.

As far as this problem goes, I'll try to write the code I need to solve this one.

Based on the input of 0 {5, 10, 2, 2, 3, 3} 15 - which would yield true. (The first element being an index int).

Code :

``` // 'a' being the array, 'i' the index, 'sum' an int to store the total, 'n' being the expected result).   static void checkSum(int[] a, int i, int sum, int n) { int total = sum; //this will set total to the value passed to the method (starts at 0) if ( i < a.length ) // if i is less than a.length (5) { total += a[i]; // total is equal to total plus the value stored in element i i += 2; // increment i by 2 to get the next value checkSum(a, i, total, n); // recur on this method passing the updated i int } else if ( total == n ) // if the problem is solved System.out.print(true); else System.out.print(false); }```

That works as long as the sum expects the method to only be run from the first element onwards, incrementing the index by 2 each time.

In {2, 5, 10, 4, 2} - 7, this wouldn't work considering the 5 and 2 would never be added together.

This is where I'm stuck! :(