Dont understand this recursion problem :(

[Maximilian]

You know its bad when you look at the answer and still don't get it lol...

http://codingbat.com/prob/p145416

Can anyone explain.. more?

 

[Tweak155]

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.

 

[Tweak155]

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]

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:

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);
}

 

[Ken g6]

I thought this problem looked familiar.

https://en.wikipedia.org/wiki/Subset_sum_problem

 

[brianmanahan]

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

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++) {
		list.add(nums[i]);
	}
	return list;
}

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

 

[mjd]

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:

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);
}

What about negative numbers? :-(

 

[Paul98]

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]

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.

 

[veri745]

What about negative numbers? :-(

Their test cases didn't include negative numbers, so obviously negative numbers are unimportant 😉

In all seriousness, though, there are definitely applications where you're dealing with non-negative numbers, so optimizations for ending early are important. In cases like packing or capacity planning (can we fill up this container exactly without wasting space), there are no negative numbers.