# Dont understand this recursion problem :(

#### Tweak155

##### Lifer
I think I get it.

So the first line is your base case needed for all recursion problems. If target exactly equals 0, then subtracting some subset of the numbers worked. Otherwise you'll be above 0 or below 0.

The next 2 lines try 2 situations. The first one assumes the first value is a possible part of the solution. The following line skips the first entry because it may not fit the solution. But since the first line tries all numbers, once you skip the first number, the following two are tried in the subsequent calls.

If neither of those lines returns true, then you must return false which is the last line. I'm assuming in Java once you return from a function, the function quits executing because this would not work in all languages.

EDIT:

I should also mention in the base statement it checks to see if START goes past the bounds of the array. If it does, you've tried your last number so this is the stopping point.

Last edited:

#### Tweak155

##### Lifer
As far as recursion goes from a general point of view, it's trying to code a solution that finds the answer based on a pattern.

So if I wanted to write a recursive function that finds X to the N power, I'd write the function in a pattern that matches how to do a power. So I'd keep passing in X * X because that is the repeated step to determine your answer.

In the problem above, you can code any pattern you'd like that would solve the problem, not just their solution.

Recursion can be really simple and extremely powerful at the same time. It's very useful. But if you don't know the theoretical limits on how many times the function will call itself, it can be pretty deadly too

#### veri745

##### Golden Member
Efficiency-wise, the solution provided is pretty bad. It will recurse in multiple situations where it doesn't have to, and in general spend quite a bit of time (if the array is large) spinning its wheels when a solution is impossible (or already found)

This is the solution I came up with:

Code:
public boolean groupSum(int start, int[] nums, int target) {

if (target == 0) {
return true;
}

if (start >= nums.length || target < 0) {
return false;
}

if (groupSum(start + 1, nums, target - nums[start])) {
return true;
}

return groupSum(start + 1, nums, target);
}

Last edited:

#### brianmanahan

##### Lifer
this would be a lot more succinct/better in groovy, or scala, or clojure, or prolog

also i hate arrays so i turned it into a list

Code:
public boolean groupSum(int start, int[] nums, int target) {
List<Integer> list = populateList(start, nums);
return recursiveGroupSum(list, target);
}

private List<Integer> populateList(int start, int[] nums) {
List<Integer> list = new ArrayList<Integer>(nums.length);
for(int i = start; i < nums.length; i++) {
}
return list;
}

public boolean recursiveGroupSum(java.util.List<Integer> list, int target) {
if (0 == target) return true;
if (list.size() == 0) return false;
java.util.List<Integer> tail = list.subList(1, list.size());
return recursiveGroupSum(tail, target - head) ||
recursiveGroupSum(tail, target);
}

#### mjd

##### Member
Efficiency-wise, the solution provided is pretty bad. It will recurse in multiple situations where it doesn't have to, and in general spend quite a bit of time (if the array is large) spinning its wheels when a solution is impossible (or already found)

This is the solution I came up with:

Code:
public boolean groupSum(int start, int[] nums, int target) {

if (target == 0) {
return true;
}

if (start >= nums.length || target < 0) {
return false;
}

if (groupSum(start + 1, nums, target - nums[start])) {
return true;
}

return groupSum(start + 1, nums, target);
}

#### Paul98

##### Diamond Member
This is what I did

// This is the end since we are ether at the end of the recursion or we put a larger value in for start than the number of elements in the array
if( start >= nums.length )
{
if( target == 0 )
return true;
if(target != 0 )
return false;
}

// these two if statements are where the work is done.
// these are the two cases we ether want to use the current target value
// OR we want to check the the target value minus the current array value

if( groupSum( start+1, nums, target-nums[start]) )
return true;

if( groupSum( start+1, nums, target ) )
return true;

return false;

// so looking at how it goes through this look at their example of 2, 4, 8 array and 10 target
// first set through first set of if statements end's up returning false
// so going through groupSum with new target = target-nums[start]
1. target = 10-2 = 8 start = 0
2. target = 8-4 = 4 start = 1
3. target = 4-8 = -4 start = 2
// then call seeing if target is 0 but it isn't so go back to previous statement
2. target = 8-4 = 4 start = 1
// now at second if statement where new target = target
4. target = 4 start = 2
// end this one here and target isn't equal to 0 so back to the first call
1. target = 10-2 = 8 start = 0
// now new target = target again
5. target = 8 start = 1
6. target = 8-8 start = 2
// now we call the last check and we found that it is true, return true through rest of the functions.

#### mv2devnull

##### Golden Member
A binary tree. A recursive search on a binary tree.

With ordered set {2,4,8} the root naturally has two subtrees; one that does include 2 in a sum and the other that does not.

Our goal is to find 9.
The subtree that does include 2 has ordered set {4,8} and should return 7. (2+7=9)
The subtree that does not include 2 has ordered set {4,8} too, but should return 9.

We continue depth-first. Alas, it turns out that no sum is 9.

Last edited: