Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
[OCP 17 book] | [OCP 11 book] | [OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]
Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2
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.
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
I, however, now only see this thing going to the right and subtracting every element from the left seqentially from target???
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
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
BTW, what does line 9 do? It's extraneous. And actually wrong.
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 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
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
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
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
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
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
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:
I don't know, it was part of the pre-written code for an exercise.
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...
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
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.
Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
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:
Henry's wrong on this one, line 9 (line 10 in my commented version) is neither extraneous nor incorrect.
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
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
Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
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;
Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
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.
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
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:
increment the start position and repeat above;
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.
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
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
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
Is there a simple explanation as to the elements of a method that employs backtracking recursion?
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
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 ...
[OCP 17 book] | [OCP 11 book] | [OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]
Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2
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 .
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
Really, though, I do appreciate everyone's efforts in this thread.
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
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
Hello. My name is Inigo Montoya. You killed my father. Prepare to die.
Don't get me started about those stupid light bulbs. |