gudii9
asked on
backtracking recursion code
public class Sum2 {
public static int targetSum = 15;
public static int[] nums = new int[]{6, 7, 8, 9};
public static void main(String args[]) {
System.out.println(" ======>Found group sum to " + targetSum + "? " + groupSum(0, nums, targetSum));
}
//public static boolean groupSum(int start, int[] nums, int target) {}
public static boolean groupSum(int start, int[] nums, int target) {
if (start >= nums.length) { // first deal with the corner case
return (target == 0);
}
if (groupSum(start + 1, nums, target - nums[start])) {
return true;
}
if (groupSum(start + 1, nums, target)) {
return true;
}
return false;
}
}
i am trying to understand above backtracking recursion code but could not. What is happening inside the code?
we have 3 if loops
1st if loop as below is base case right
if (start >= nums.length) { // first deal with the corner case
return (target == 0);
}
second if calls again top recursive containing method
if (groupSum(start + 1, nums, target - nums[start]))
third second if calls again top recursive containing method with different set of arguments??
if (groupSum(start + 1, nums, target - nums[start]))
please advise
ASKER
public class Sum2 {
public static boolean groupSum(int start, int[] nums, int target) {
System.out.println(start + " " + target);
if (target == 0) { // first deal with the corner case
return true;
}
if (start == nums.length) {
return false;
}
if (!groupSum(start + 1, nums, target - nums[start])) {
return groupSum(start + 1, nums, target);
}
else {
return true;
}
}
public static void main(String args[]) {
boolean b = groupSum(0, new int[] { 2, 4, 8 }, 10);
}
}
0 101 8
2 4
3 -4
3 4
2 8
3 0
ABOVE Passed all tests not sure how? please advise
ASKER
not clear on why we are using function call within the if condition?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
what is differeence between below two approaches?
ID: 41875119
ID: 41875125
ID: 41875119
ID: 41875125
ASKER
The second if statement includes the current array element in the group sum.why we need to include in one case and should not include in other case?
The third if statement does not include the current array element in the group sum.
ASKER
at line 3 start
at line 4 call groupSum method
at line 5 ( start is 0 , target is 5 )
at line 7 recursive call
at line 5 ( start is 1 , target is 1 )
at line 7 recursive call
at line 5 ( start is 2 , target is -4 )//how start is 2 i thought start is 1 as 0+1 is 1 and how target is -4 here i thought target is 5-4 ie target - nums[start] is 1??
at line 4 call groupSum method
at line 5 ( start is 0 , target is 5 )
at line 7 recursive call
at line 5 ( start is 1 , target is 1 )
at line 7 recursive call
at line 5 ( start is 2 , target is -4 )//how start is 2 i thought start is 1 as 0+1 is 1 and how target is -4 here i thought target is 5-4 ie target - nums[start] is 1??
ASKER
at line 7 return false //how this is false?
if(groupSum(start + 1, nums, target - nums[start]))return true;
if(groupSum(start + 1, nums, target - nums[start]))return true;
ASKER
Your output //with my comments.
0 10 // first call to the groupSum method
1 8 // first element is equal to 2, 10 - 2 is equal to 8
2 4 // second element is 4, 8 - 4 is 4
3 -4 // third element is 8, 4 -8 is -4 this concludes first group
i understood clearly till above.
struggling to understand afterwards
3 4 // this is trying a second group 10 - 2 - 4 is 4 doesn't include the third element // why third element skipped?
2 8 // this is starting to try third group 10 - 2 is 8 //what is second group what is third group...what you mean by group??
3 0 // this concludes third group 10 - 2 - 8 is 0 the second element was not included //completely lost with what it mean by group and third group ? is group same as branch? i am not clear on branch either?
0 10 // first call to the groupSum method
1 8 // first element is equal to 2, 10 - 2 is equal to 8
2 4 // second element is 4, 8 - 4 is 4
3 -4 // third element is 8, 4 -8 is -4 this concludes first group
i understood clearly till above.
struggling to understand afterwards
3 4 // this is trying a second group 10 - 2 - 4 is 4 doesn't include the third element // why third element skipped?
2 8 // this is starting to try third group 10 - 2 is 8 //what is second group what is third group...what you mean by group??
3 0 // this concludes third group 10 - 2 - 8 is 0 the second element was not included //completely lost with what it mean by group and third group ? is group same as branch? i am not clear on branch either?
ASKER
if (!groupSum(start + 1, nums, target - nums[start])) {
return groupSum(start + 1, nums, target);
}
no clue what above lines means??
what is differeence between below two approaches?I don't know. They look the same to me.
why we need to include in one case and should not include in other case?We are looking for a group that sums to the target. We keep trying different groups until we find the right group.
how start is 2 i thought start is 1 as 0+1 is 1We made a call from line 7 which added 1 to start to get 2
how target is -4 here i thought target is 5-4it was 1 and 5 was subtracted to get -4
at line 7 return false //how this is false?The target was not equal to 0
what you mean by group??The original challenge at CodingBat asked
Given an array of ints, is it possible to choose a group of some of the ints, such that the group sums to the given target?So, I mean a group of ints.
Let's begin again. You asked several times for a graphical explanation. The following is my attempt at that. Let's try to follow the thread of execution for my last code(Sum4). Please look at this illustration. The JVM executes my code using a single thread. When a method is called the thread starts to execute it. But, when another method is called within the first method then the thread stops executing the first method and begins executing the second method. When it finishes the second method, it returns to where it left off in the first method and continues execution . The call stack is where the JVM stores data about the first method while the second method is being executed. Look at
https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-2.html#jvms-2.5.2
https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-2.html#jvms-2.6
The illustration graphically shows the thread of execution. Above here I typed out the steps manually. Please refer to that. The thread start out in the color yellow. Main was called to start the program. The println method was called and then the groupSum method(line 5) was called(start is 0, target is red5). At line 7 a recursive call was made. This is a second method as far as the thread is concerned. So, the JVM stores the data of the first method on the "call stack" and the thread starts executing the second call(shown in orange color). The second call makes another recursive call. This third call is shown in the color red. At this point in time. We have the first two calls on the stack while we execute the third. A Stack is a last-in-first-out data structure. See
http://docs.oracle.com/javase/8/docs/api/java/util/Stack.html
When the color red ends in false(within if statement), then the thread continues where it left off with the color orange. When the orange ends with false, the thread finally gets back to the first call which is shown in yellow. This results in true and finally gets back to the println method and prints the output. The numbers in the illustration in light blue are (start, target).
Hopefully, in the next few days, some experts will add to this discussion. My explanation was rudimentary.
I made an error in my manual steps and in the illustration. The orange line should have dipped down to line 9 which would return false to line 7 and turn back to yellow.
Incidentally, I ignored the calls to main and println in my call stack count. I was just concentrating on the calls to the groupSum method.
I made an error in my manual steps and in the illustration. The orange line should have dipped down to line 9 which would return false to line 7 and turn back to yellow.
Incidentally, I ignored the calls to main and println in my call stack count. I was just concentrating on the calls to the groupSum method.
ASKER
what is differeence between below two approaches?
I don't know. They look the same to me.
if (!groupSum(start + 1, nums, target - nums[start])) {
return groupSum(start + 1, nums, target);
}
one has negation ! case right other does not? do you mean even then both does same thing?
ASKER
so now threads is one other new piece to this whole puzzle.
when thread 1 created and called and when thread 2 created and called?
any good video tutorial on java back tracking recursion not regular recursion?
when thread 1 created and called and when thread 2 created and called?
any good video tutorial on java back tracking recursion not regular recursion?
ASKER
i like below explanation looking for some graphical representation as below
http://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html
http://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html
one has negation ! case right other does not? do you mean even then both does same thing?Yes, I meant that they do the same thing. Who wrote the second version?
when thread 1 created and called and when thread 2 created and called?I am sure what you are asking here. The program only has one thread.
any good video tutorial on java back tracking recursion not regular recursion?I already posted
https://www.experts-exchange.com/questions/28971483/groupSum-challege.html?anchorAnswerId=41863965#a41863965
i like below explanation looking for some graphical representation as belowWhy do you like it?
ASKER
i liked it because of the diagram .
ASKER
I would like to discuss different approaches here like below
if (!groupSum(start + 1, nums, target - nums[start])) {
return groupSum(start + 1, nums, target);
}
if (!groupSum(start + 1, nums, target - nums[start])) {
return groupSum(start + 1, nums, target);
}
ASKER
Open in new window
above gave below output
0 10
1 8
2 4
3 -4
3 4
2 8
3 0
i was clear till
0 10
1 8
2 4
3 -4
i was not clear on later
3 4
2 8
3 0
then how we are starting from start 3 and going to 2 backwards? is it same brach going backwards? or is it new branch?