Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# backtracking recursion  code

Posted on 2016-11-04
Medium Priority
92 Views
``````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]))

0
Question by:gudii9
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 14
• 4

LVL 7

Author Comment

ID: 41875119
``````public class Sum2 {

public static boolean groupSum(int start, int[] nums, int target) {
System.out.println(start + " " + 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;
}

public static void main(String args[]) {
boolean b = groupSum(0, new int[] { 2, 4, 8 }, 10);
}
}
``````

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?
0

LVL 7

Author Comment

ID: 41875125
``````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 10
1 8
2 4
3 -4
3 4
2 8
3 0

0

LVL 7

Author Comment

ID: 41875126
not clear on why we are using function call within the if condition?
0

LVL 28

Accepted Solution

rrz earned 2000 total points
ID: 41875490
The first if statement is the base case. It terminates the recursion.
The second if statement includes the current array element in the group sum.
The third if statement does not include the current array element in the group sum.
not clear on why we are using function call within the if condition?

This allows the execution to keep searching all the possibilities even after a false was returned. If the call was not in a if statement, then the boolean that is returned would be returned to line 23 and the execution would end.
https://www.experts-exchange.com/questions/28979050/Non-recursive-backtracking-using-a-stack.html#a41860708

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
3 4 // this is trying a second group 10 - 2 - 4 is 4  doesn't include the third element
2 8 // this is starting to try third group  10 - 2 is 8
3 0 // this concludes third group 10 - 2 - 8 is 0  the second element was not included

I think what we need to do is follow the execution of the code manually. That way we can see what the JVM is doing. Please consider using a bare bones code such as the following.
``````public class Sum4{
public static int[] nums = new int[]{4, 5};
public static void main(String args[]) {
System.out.println("Found group sum to 5? " + groupSum(0, nums, 5)); }
public static boolean groupSum(int start, int[] nums, int target) {
if(start >= nums.length)return(target == 0);
if(groupSum(start + 1, nums, target - nums[start]))return true;
if(groupSum(start + 1, nums, target))return true;
return false;
}
}
``````
Here is my attempt at stepping through the code(Sum4) manually.

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 )
at line 6 return false
at line 7 return false
at line 8 recursive call
at line 5 ( start is 2 , target is 1 )
at line 6 return false
at line 8 return false
at line 8 recursive call
at line 5 ( start is 1 , target is 5 )
at line 7 recursive call
at line 5 (start is 2, target is 0)
at line 6 return true
at line 7 return true
at line 4 print "Found group sum to 5? true"
0

LVL 7

Author Comment

ID: 41876250
what is differeence between below two approaches?

ID: 41875119
ID: 41875125
0

LVL 7

Author Comment

ID: 41876257
The second if statement includes the current array element in the group sum.
The third if statement does not include the current array element in the group sum.
why we need to include in one case and should not include in other case?
0

LVL 7

Author Comment

ID: 41876261
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??
0

LVL 7

Author Comment

ID: 41876263
at line 7 return false //how this is false?
if(groupSum(start + 1, nums, target - nums[start]))return true;
0

LVL 7

Author Comment

ID: 41876266
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

LVL 7

Author Comment

ID: 41876290
``````if (!groupSum(start + 1, nums, target - nums[start])) {
return groupSum(start + 1, nums, target);
}
``````

no clue what above lines means??
0

LVL 28

Expert Comment

ID: 41876328
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 1
We made a call from line 7 which added 1 to start to get 2
how target is -4 here i thought target is 5-4
it 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).
0

LVL 28

Expert Comment

ID: 41876346
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.
0

LVL 7

Author Comment

ID: 41876498
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?
0

LVL 7

Author Comment

ID: 41876499
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?
0

LVL 7

Author Comment

ID: 41876510
i like below explanation looking for some graphical representation as below

http://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html
0

LVL 28

Expert Comment

ID: 41876638
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?
https://www.experts-exchange.com/questions/28971483/groupSum-challege.html#a41863965
i like below explanation looking for some graphical representation as below
Why do you like it?
0

LVL 7

Author Comment

ID: 41880975
i liked it because of the diagram .
0

LVL 7

Author Comment

ID: 41886920
I would like to discuss different approaches here like below

if (!groupSum(start + 1, nums, target - nums[start])) {
return groupSum(start + 1, nums, target);
}
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

INTRODUCTION Working with files is a moderately common task in Java. Â For most projects hard coding the file names, using parameters in configuration files, or using command-line arguments is sufficient. Â  However, when your application has viâ€¦
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the bâ€¦
Viewers learn how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Downâ€¦