• Guest, The rules for the P & N subforum have been updated to prohibit "ad hominem" or personal attacks against other posters. See the full details in the post "Politics and News Rules & Guidelines."
  • Community Question: What makes a good motherboard?

Dont understand this recursion problem :(

Tweak155

Lifer
Sep 23, 2003
11,329
206
106
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
Sep 23, 2003
11,329
206
106
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
Oct 11, 2007
1,163
4
81
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
Sep 2, 2006
20,337
2,361
126
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++) {
		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

Member
Jan 3, 2007
135
0
76
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);
}
What about negative numbers? :-(
 

Paul98

Diamond Member
Jan 31, 2010
3,690
133
106
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
Apr 13, 2010
1,322
52
91
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:

veri745

Golden Member
Oct 11, 2007
1,163
4
81
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.
 
Last edited:

ASK THE COMMUNITY