Two Laptop Bag*
The moose likes Java in General and the fly likes Backtracking recursion problems. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Backtracking recursion problems." Watch "Backtracking recursion problems." New topic
Author

Backtracking recursion problems.

James Brooks
Gunslinger
Ranch Hand

Joined: Aug 17, 2006
Posts: 165
Ladies/gents,

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]


Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
Jeanne Boyarsky
author & internet detective
Marshal

Joined: May 26, 2003
Posts: 31054
    
162

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.

In your code, we have:
  • 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.


    [Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
    Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
    James Brooks
    Gunslinger
    Ranch Hand

    Joined: Aug 17, 2006
    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.

    In your code, we have:
  • 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

    Joined: Aug 17, 2006
    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

    Joined: Aug 17, 2006
    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40

    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


    Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
    James Brooks
    Gunslinger
    Ranch Hand

    Joined: Aug 17, 2006
    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40

    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40

    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40

    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

    Joined: Aug 17, 2006
    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

    Joined: Aug 17, 2006
    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

    Joined: Aug 17, 2006
    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40

    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

    Joined: Aug 17, 2006
    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40

    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

    Joined: Jan 17, 2006
    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.

    Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
    Henry Wong
    author
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40


    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40

    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

    Joined: Aug 17, 2006
    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

    Joined: Jan 17, 2006
    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

    Joined: Jan 17, 2006
    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

    Joined: Aug 17, 2006
    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40

    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40

    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

    Joined: Aug 17, 2006
    Posts: 165
    Edit: didn't see Henry's post.
    James Brooks
    Gunslinger
    Ranch Hand

    Joined: Aug 17, 2006
    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40

    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

    Joined: Aug 17, 2006
    Posts: 165
    Well, I'll keep searching, thanks for the help so far!
    Jeanne Boyarsky
    author & internet detective
    Marshal

    Joined: May 26, 2003
    Posts: 31054
        
    162

    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

    Joined: Aug 17, 2006
    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
    Sheriff

    Joined: Sep 28, 2004
    Posts: 19059
        
      40

    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

    Joined: Aug 17, 2006
    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

    Joined: Aug 17, 2006
    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!
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Backtracking recursion problems.