Link to home
Start Free TrialLog in
Avatar of gudii9
gudii9Flag for United States of America

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;
		}
}

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
Avatar of gudii9
gudii9
Flag of United States of America image

ASKER

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?
Avatar of gudii9

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);
	}
}

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
Avatar of gudii9

ASKER

not clear on why we are using function call within the if condition?
ASKER CERTIFIED SOLUTION
Avatar of rrz
rrz
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of gudii9

ASKER

what is differeence between below two approaches?

ID: 41875119
ID: 41875125
Avatar of gudii9

ASKER

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?
Avatar of gudii9

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??
Avatar of gudii9

ASKER

at line 7 return false //how this is false?
if(groupSum(start + 1, nums, target - nums[start]))return true;
Avatar of gudii9

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?
Avatar of gudii9

ASKER

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

Open in new window


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 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. User generated image  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.
Avatar of gudii9

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?
Avatar of gudii9

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?
Avatar of gudii9

ASKER

i like below explanation looking for some graphical representation as below

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 below
Why do you like it?
Avatar of gudii9

ASKER

i liked it because of the diagram .
Avatar of gudii9

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);
            }