Solved

backtracking recursion  code

Posted on 2016-11-04
19
41 Views
Last Modified: 2016-11-14
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;
		}
}

Open in new window


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
0
Comment
Question by:gudii9
  • 14
  • 4
19 Comments
 
LVL 7

Author Comment

by:gudii9
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);
	}
}

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

Author Comment

by:gudii9
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);
	}
}

Open in new window

0 10
1 8
2 4
3 -4
3 4
2 8
3 0

ABOVE Passed all tests not sure how? please advise
0
 
LVL 7

Author Comment

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

Accepted Solution

by:
rrz earned 500 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.  
Please keep in mind the  post made by James Bilous at
https://www.experts-exchange.com/questions/28979050/Non-recursive-backtracking-using-a-stack.html#a41860708  
 
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
 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;
	}
}

Open in new window

  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

by:gudii9
ID: 41876250
what is differeence between below two approaches?

ID: 41875119
ID: 41875125
0
 
LVL 7

Author Comment

by:gudii9
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

by:gudii9
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

by:gudii9
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

by:gudii9
ID: 41876266
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
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 
LVL 7

Author Comment

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

Open in new window


no clue what above lines means??
0
 
LVL 27

Expert Comment

by:rrz
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. Thread of execution  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 27

Expert Comment

by:rrz
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

by:gudii9
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

by:gudii9
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

by:gudii9
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 27

Expert Comment

by:rrz
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?
I already posted
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

by:gudii9
ID: 41880975
i liked it because of the diagram .
0
 
LVL 7

Author Comment

by:gudii9
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

For customizing the look of your lightweight component and making it look lucid like it was made of glass. Or: how to make your component more Apple-ish ;) This tip assumes your component to be of rectangular shape and completely opaque. (COD…
After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now