# Backtracking recursion problems.

James Brooks
Gunslinger
Ranch Hand
Posts: 165

The below code is a method used to determine if an array contains any group of numbers that, when summed, equal the target passed to the method. This type of recursion really gave me fits during my undergrad DSA class (Towers of Hanoi, etc), and I'm starting to think it may be above my level of brainpower. I can do normal recursion (fibonacci, factorial, etc), but not this kind here. I will be eternally grateful if someone can break this down to me so that I can finally understand it. Is there some way that I can think about such problems or analyze them so that I can 'see' the solution I want to implement? My book is worthless for this topic, at least for a dummy like me , and although I've scoured the internet, I still can't find anything that helps greatly.

[edited so doesn't scroll horizontally]

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34973
378
Patrick,
You didn't say what is happening that you aren't expecting. I'll add my observations here, but that information is important.

Whenever I do recursion, I write down (or say aloud or think about) what the base case and recursive case is.

• base case - we've already looked at all the elements and now have a logically empty array. If the remaining target isn't zero, we don't have a match
• recursive/inductive case - logically remove the first element from both the array and the target.

• This seems good, you are progressing towards a smaller array each time and making progress on solving the problem each time.

I see two problems:
• 1) I don't understand what "if (groupSum(start + 1, nums, target)) return true;" is meant to do
• 2) If the recursive call "groupSum(start + 1, nums, target - nums[start])" returns false, you want to return false to the user. Your code doesn't do that.

• Basically, I think you made the problem more complex than it needs to be. One base case and one recursive case should be enough.

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Jeanne Boyarsky wrote:Patrick,
You didn't say what is happening that you aren't expecting. I'll add my observations here, but that information is important.

Whenever I do recursion, I write down (or say aloud or think about) what the base case and recursive case is.

• base case - we've already looked at all the elements and now have a logically empty array. If the remaining target isn't zero, we don't have a match
• recursive/inductive case - logically remove the first element from both the array and the target.

• This seems good, you are progressing towards a smaller array each time and making progress on solving the problem each time.

I see two problems:
• 1) I don't understand what "if (groupSum(start + 1, nums, target)) return true;" is meant to do
• 2) If the recursive call "groupSum(start + 1, nums, target - nums[start])" returns false, you want to return false to the user. Your code doesn't do that.

• Basically, I think you made the problem more complex than it needs to be. One base case and one recursive case should be enough.

Thanks for the response. I have learned to identify the base case first. If you see my comments, what I don't understand: in the first call, the selection:
if (groupSum(start + 1, nums, target - nums[start])) return true;
will be chosen, and this looks to me as if start is incremented at the beginning, meaning that comparisons are only made from start=1, and not start=0. As for the items that you see problems with:

• 1) Not sure, either. This is not my code. I wish I could code and understand these methods, but it's just not clicking.
2) The method does have a 'return false' statement at the very end, so it looks like it 'catches' all unsolvable situations.

• So, what I'm wondering: is start = 0 ever analyzed, and if so, where? I don't see it!

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Oops, sorry, I do see that nums[start] is subtracted. For some reason, I was reading it as nums[start+1]. Well, that at least takes some of the mystery out of this:

I, however, now only see this thing going to the right and subtracting every element from the left seqentially from target???

James Brooks
Gunslinger
Ranch Hand
Posts: 165
I guess what I'm trying to say is that it seems to just go to the right, subtracting each element from target. If this is the case (it's not, I know, but it's what it looks like to me), then this wouldn't work if your group that could add up to target is not all clustered together. Here's what I see it doing?

Henry Wong
author
Marshal
Posts: 21496
84
I, however, now only see this thing going to the right and subtracting every element from the left seqentially from target???

Yup, that's what it does. It wll keep subtracting everything from target, until there is nothing to subtract, then ... it will run (line 3) the code that checks to see if target is zero. And if the array sums up to the target, what should the target be when you subtract everything?

BTW, what does line 9 do? It's extraneous. And actually wrong.

Henry

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Henry Wong wrote:
I, however, now only see this thing going to the right and subtracting every element from the left seqentially from target???

Yup, that's what it does. It wll keep subtracting everything from target, until there is nothing to subtract, then ... it will run (line 3) the code that checks to see if target is zero. And if the array sums up to the target, what should the target be when you subtract everything?

BTW, what does line 9 do? It's extraneous. And actually wrong.

Henry

Hi Henry. Could you see my post just above yours (probably written while you were responding), and answer my doubt:

"I guess what I'm trying to say is that it seems to just go to the right, subtracting each element from target. If this is the case (it's not, I know, but it's what it looks like to me), then this wouldn't work if your group that could add up to target is not all clustered together. "

Henry Wong
author
Marshal
Posts: 21496
84
BTW, what does line 9 do? It's extraneous. And actually wrong.

Okay, since you changed the code...

What does this line do? It's extraneous. And actually wrong.

Henry

Henry Wong
author
Marshal
Posts: 21496
84
I guess what I'm trying to say is that it seems to just go to the right, subtracting each element from target. If this is the case (it's not, I know, but it's what it looks like to me),

Yup, this is the case.... and it's correct.

then this wouldn't work if your group that could add up to target is not all clustered together.

Show me an example where this won't work? Meaning.... is there a case where you subtract every element from the sum, and the sum won't end up as zero?

Henry

Henry Wong
author
Marshal
Posts: 21496
84
And this post is for a personal gripe of mine -- feel free to ignore this one...

It bothers me that people forget that public and private still applies -- even for recursion. Meaning...

What is the purpose of the start parameter? IMO, it is an interium value that the recursive algorithm use to pass state from one call to another. Why is it exposed? Why should the user of the class even need to provide a start?

It may be better to hide that parameter, and provide a cleaner public interface... like so...

Henry

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Henry Wong wrote:
I guess what I'm trying to say is that it seems to just go to the right, subtracting each element from target. If this is the case (it's not, I know, but it's what it looks like to me),

Yup, this is the case.... and it's correct.

then this wouldn't work if your group that could add up to target is not all clustered together.

Show me an example where this won't work? Meaning.... is there a case where you subtract every element from the sum, and the sum won't end up as zero?

Henry

OK, here's an example of what I'm talking about, this function call: groupSum(0, {10, 2, 2, 5}, 17)

if I subract 10, 2, 2, and 5 from 17, I get 7, 5, 3, and -2, respectively. Yes, I know that this code, when compiled and run, works (although I still don't understand 100%), but what I was saying is: this function, then, cannot simply subtract every element, hoping to come up with zero. How, then, does this method skip one of the 2's? All I 'see' is a recursive pseudocode:

Skip to the next element and subtract the current element from target.

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Henry Wong wrote:
BTW, what does line 9 do? It's extraneous. And actually wrong.

Okay, since you changed the code...

What does this line do? It's extraneous. And actually wrong.

Henry

I don't know, it was part of the pre-written code for an exercise.

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Henry Wong wrote:And this post is for a personal gripe of mine -- feel free to ignore this one...

It bothers me that people forget that public and private still applies -- even for recursion. Meaning...

What is the purpose of the start parameter? IMO, it is an interium value that the recursive algorithm use to pass state from one call to another. Why is it exposed? Why should the user of the class even need to provide a start?

It may be better to hide that parameter, and provide a cleaner public interface... like so...

Henry

Start is used to allow a user to select the array element to start at, instead of defaulting to the start of the array, nums[0]. This is an academic exercise, so I guess they think it doesn't have to make much sense The code was copied from the webpage that contained this tutorial, so I didn't pay much attention to the modifiers. I understand that we should 'protect', or 'hide' everything to the extent that we can.

Henry Wong
author
Marshal
Posts: 21496
84
OK, here's an example of what I'm talking about, this function call: groupSum(0, {10, 2, 2, 5}, 17)

if I subract 10, 2, 2, and 5 from 17, I get 7, 5, 3, and -2, respectively. Yes, I know that this code, when compiled and run, works (although I still don't understand 100%), but what I was saying is: this function, then, cannot simply subtract every element, hoping to come up with zero. How, then, does this method skip one of the 2's? All I 'see' is a recursive pseudocode:

Nope, this is *not* what your code does. If you need to test for the sum for any combo of numbers, then this solution clearly doesn't work -- you have some work to do.... which leads to the next question...

I don't know, it was part of the pre-written code for an exercise.

It was probably an attempt to remove the first element from the sum -- which is wrong if you want all combos. You need to have a loop that removes one element (for each of the elements), and make the recursive call for each case (of one element removed).

Henry

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Henry Wong wrote:

Nope, this is *not* what your code does. If you need to test for the sum for any combo of numbers, then this solution clearly doesn't work -- you have some work to do.... which leads to the next question...

The solution does pass all validity checks, including any group of numbers (that sum up to targer) within another group of numbers, even when not in order. If I take line 9 out, which you said is wrong, the solution doesn't pass the validity checks. I'm not saying you're wrong, just telling you what happened when I took it out. If I'm not allowed to post links, sorry, just edit this, but I got this problem here: http://www.javabat.com/prob/p145416

Well, if I break line 5 down:

groupSum(start+1 //passes the next array subscript to be used

, nums, //passes the array

target-nums[start])) //passes a new target value, consisting of the target-the current value in the nums array, at the start subscript

So, to me, this: subtracts the current array value from target, then goes on to the next array value and keeps doing the same. Why am I not seeing what this function does?

Henry Wong
author
Marshal
Posts: 21496
84
The solution does pass all validity checks, including any group of numbers (that sum up to targer) within another group of numbers, even when not in order.

Really?!?! This passes??? Let me check.... [goes and check] ....

... I'm back...

First, apologies... The solution does pass. It's actually a very elegant algorithm. Let's me write up how it works in the next post.

Henry

Garrett Rowe
Ranch Hand
Posts: 1296

Henry's wrong on this one, line 9 (line 10 in my commented version) is neither extraneous nor incorrect. It solves the case where nums[start] is not part of the solution.

Henry Wong
author
Marshal
Posts: 21496
84

Here's how it works... let's use your example.

OK, here's an example of what I'm talking about, this function call: groupSum(0, {10, 2, 2, 5}, 17)

if I subract 10, 2, 2, and 5 from 17, I get 7, 5, 3, and -2, respectively. Yes, I know that this code, when compiled and run, works (although I still don't understand 100%), but what I was saying is: this function, then, cannot simply subtract every element, hoping to come up with zero. How, then, does this method skip one of the 2's? All I 'see' is a recursive pseudocode:

Here is how the "2" is skipped. First, let's take this example down to where it doesn't match...

Now, let's backtrack, but.... not all the way. Let's backtrack to here (two levels back)...

Now, let's take the other route, where the start element is skipped, but it is not subtracted from the total...

Now, of course, the algorithm went through tons of other routes before getting to this point. But from this small example, you can see how any number can be removed. And how it can remove two numbers. etc. etc. etc.

Hope this helps,
Henry

Henry Wong
author
Marshal
Posts: 21496
84
Henry's wrong on this one, line 9 (line 10 in my commented version) is neither extraneous nor incorrect.

Yeah, I kinda already ate crow on this one -- but I can eat some more ...

Anyway, see my previous post on how everything works.

Henry

James Brooks
Gunslinger
Ranch Hand
Posts: 165
So, then, this is a 'depth-first' algorithm? I still don't see the 'backtrack' mechanism. I've written the steps out on paper, and all I 'see' is:

subtract each element from target, going from left to right;
if target is 0 after above
true;
else
increment the start position and repeat above;

Garrett Rowe
Ranch Hand
Posts: 1296
Henry Wong wrote:
Henry's wrong on this one, line 9 (line 10 in my commented version) is neither extraneous nor incorrect.

Yeah, I kinda already ate crow on this one -- but I can eat some more ...

Anyway, see my previous post on how everything works.

Henry

I posted before I saw that you saw your mistake. But lets be fair, crows are delicious!

Garrett Rowe
Ranch Hand
Posts: 1296
Patrick Brooks wrote:So, then, this is a 'depth-first' algorithm? I still don't see the 'backtrack' mechanism. I've written the steps out on paper, and all I 'see' is:

subtract each element from target, going from left to right;
if target is 0 after above
true;
else
increment the start position and repeat above;

But you must note that since this is a recursive algorithm, that the start position is not always the first position in the array, and so the effect is "skipping" an arbitrary position in the until all possible combinations have been attempted or a solution is found.

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Garrett Rowe wrote:
Patrick Brooks wrote:So, then, this is a 'depth-first' algorithm? I still don't see the 'backtrack' mechanism. I've written the steps out on paper, and all I 'see' is:

subtract each element from target, going from left to right;
if target is 0 after above
true;
else
increment the start position and repeat above;

But you must note that since this is a recursive algorithm, that the start position is not always the first position in the array, and so the effect is "skipping" an arbitrary position in the until all possible combinations have been attempted or a solution is found.

Hi Garrett,

I accept that this is how this method works, but I still don't understand. Using my example from earlier, groupSum(0, {10, 2, 2, 5}, 17), as Henry said,
groupSum(0, {10, 2, 2, 5}, 17) //first
groupSum(1, {10, 2, 2, 5}, 7) //next
groupSum(2, {10, 2, 2, 5}, 5) //next
groupSum(3, {10, 2, 2, 5}, 3) //next
groupSum(4, {10, 2, 2, 5}, -2) //next

and boom, now we hit our condition if(start>nums.length()). So, since -2 != 0, we have to run this again, but what stops it from recursively 'unwinding' all the way back to the beginning? That's what I see it doing, and why I see it continuting the above pattern at each array element.

Henry Wong
author
Marshal
Posts: 21496
84
Patrick Brooks wrote:So, then, this is a 'depth-first' algorithm? I still don't see the 'backtrack' mechanism. I've written the steps out on paper, and all I 'see' is:

A backtrack is when a method returns false. It then goes and tries the next alternate route. This can be done by any of the methods calls on the way down -- during the way back up.

increment the start position and repeat above;

Keep in mind that this is not just done by the top call. This is done by all the calls on the way down. So... as Garrett mentioned, this "start" value can be at any location.

Henry

Henry Wong
author
Marshal
Posts: 21496
84
and boom, now we hit our condition if(start>nums.length()). So, since -2 != 0, we have to run this again, but what stops it from recursively 'unwinding' all the way back to the beginning? That's what I see it doing, and why I see it continuting the above pattern at each array element.

Because the code is not designed to unwind all the way to the beginning (for false). It is only designed to completely unwind for true. For false, it is only designed to unwind by one -- meaning the "if" failed, so it must do "then". In fact, in my explanation, where I unwind by two, I skipped a few steps, here is the complete call path...

Henry

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Edit: didn't see Henry's post.

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Henry Wong wrote:
and boom, now we hit our condition if(start>nums.length()). So, since -2 != 0, we have to run this again, but what stops it from recursively 'unwinding' all the way back to the beginning? That's what I see it doing, and why I see it continuting the above pattern at each array element.

Because the code is not designed to unwind all the way to the beginning (for false). It is only designed to completely unwind for true. For false, it is only designed to unwind by one -- meaning the "if" failed, so it must do "then". In fact, in my explanation, where I unwind by two, I skipped a few steps, here is the complete call path...

Henry

OK, I follow the calls you made, and see the tree that it traverses, but still couldn't code this method from scratch for a different application to save my life, and still don't 'see' the mechanism that makes it try the different paths. Is there a simple explanation as to the elements of a method that employs backtracking recursion? Everything I've found talks about trees and depth, and now I'm just looking for the breakdown of how to implement this.

Henry Wong
author
Marshal
Posts: 21496
84
Is there a simple explanation as to the elements of a method that employs backtracking recursion?

How about this? Let me comment your code like crazy and hope it clicks. Otherwise, Sorry... I don't know what else to tell you.

Henry

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Well, I'll keep searching, thanks for the help so far!

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34973
378
I see the problem. Y'all post to often and there were simultaneous comments .

Henry Wong wrote:
Henry's wrong on this one, line 9 (line 10 in my commented version) is neither extraneous nor incorrect.

Yeah, I kinda already ate crow on this one -- but I can eat some more ...

I thought the same thing as Henry. Good company to be wrong with at least .

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Jeanne Boyarsky wrote:I see the problem. Y'all post to often and there were simultaneous comments .

Henry Wong wrote:
Henry's wrong on this one, line 9 (line 10 in my commented version) is neither extraneous nor incorrect.

Yeah, I kinda already ate crow on this one -- but I can eat some more ...

I thought the same thing as Henry. Good company to be wrong with at least .

Post too often? This coming from a moderator? Maybe I just figured I'd make up for my lack of programming skills with a high post count Really, though, I do appreciate everyone's efforts in this thread.

Henry Wong
author
Marshal
Posts: 21496
84
Really, though, I do appreciate everyone's efforts in this thread.

Well, I would still feel better if we can help you though this... We commented the heck out of your code -- in fact, there are twice as many comments than actual code. We gave you the complete call path -- along with an explanation of the relavant routes.

Frankly, I don't know of any other ways of explaning the solution... I'm out of ideas.... Perhaps if you can elaborate on what (or why) you are still confused.

Henry

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Henry Wong wrote:
Really, though, I do appreciate everyone's efforts in this thread.

Well, I would still feel better if we can help you though this... We commented the heck out of your code -- in fact, there are twice as many comments than actual code. We gave you the complete call path -- along with an explanation of the relavant routes.

Frankly, I don't know of any other ways of explaning the solution... I'm out of ideas.... Perhaps if you can elaborate on what (or why) you are still confused.

Henry

You know, I can't pinpoint it; I just simply don't know how I would code a similar method, since I don't understand how it does what it does (I mean, what makes it backtrack and try alternate paths). Everyone keeps telling me that it's due to recursive method calls, but that really doesn't mean much to me. Sorry for being so thick on this, I just really don't 'get it'.

James Brooks
Gunslinger
Ranch Hand
Posts: 165
Update: one of the members on here is my personal tutor, and after analyzing a case, method call by method call, with 5 array elements, I've finally 'got it', and see where/why the method branches off and tries all lower possibilities before returning false. Coding a similar method may be a different story altogether, but at least I understand it now and have somewhere to start from. Thanks again for the help!