We help IT Professionals succeed at work.

groupSum challege

574 Views
Last Modified: 2016-12-06
Hi,

I am working on below challenge

http://codingbat.com/prob/p145416

Recursion-2 > groupSum
prev  |  next  |  chance
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? This is a classic backtracking recursion problem. Once you understand the recursive backtracking strategy in this problem, you can use the same pattern for many problems to search a space of choices. Rather than looking at the whole array, our convention is to consider the part of the array starting at index start and continuing to the end of the array. The caller can specify the whole array simply by passing start as 0. No loops are needed -- the recursive calls progress down the array.

groupSum(0, [2, 4, 8], 10) → true
groupSum(0, [2, 4, 8], 14) → true
groupSum(0, [2, 4, 8], 9) → false

I have not understand above description. please advise
Comment
Watch Question

zzynxSr. Software engineer
CERTIFIED EXPERT

Commented:
You make the sum of the ints you encounter and check if that equals to the give target sum.
AndyAinscowFreelance programmer / Consultant
CERTIFIED EXPERT

Commented:
If I understand it correctly the question is something like this.

Is it possible to select some of the following values - 1, 5, 8, 23, 9, 14, 4 - to add together to make eg. 36
ste5anSenior Developer
CERTIFIED EXPERT

Commented:
Well, have you read the theory about it?

- Recursion and Recursive Backtracking
- Backtracking

In short:

Backtracking is possible, when you have a input set and you're looking for a sub-set which fulfills a certain condition. This condition must be expressible in two ways. It must be possible to form a negative over an input set, which tells us that this set is and it derived version cannot fullfil the condition. And a positive which tells us the the given set fulfills the condition exactly. The backtracking recursion now operates on the input set and can either reduce it and test the conditions or it can start with the smallest sub-sets and expand them.


Spoiler: The tests are again imho incomplete. Sum(ø) != 0 with Sum({e1,..,en}) = Σ e1 + .. + en.
CERTIFIED EXPERT
Top Expert 2016

Commented:
I have not understand above description. please advise
if any combination of array elements would sum-up to a total equal to the given target value, we get true. otherwise false.

the point in this challenge is to call the recursive function two times for index+1: one where the current element was used for the sum and a second if the first recursion failed and the current value was not used. the first call would subtract nums[index] from target. if the first call returns false, a second recursive call was made passing the given target and hence skipping the current element.

pseudo-code:
<<REMOVED BY TA - saved off for reinstatement if RA and mods agree. >>
Sara

Author

Commented:
You make the sum of the ints you encounter and check if that equals to the give target sum.


groupSum(0, [2, 4, 8], 10) → true

2+4+8 is 14 which is not equal to 10 so above should be false right? how above is true?
AndyAinscowFreelance programmer / Consultant
CERTIFIED EXPERT

Commented:
Look at my earlier example and description.  repeated:
If I understand it correctly the question is something like this.

Is it possible to select some of the following values - 1, 5, 8, 23, 9, 14, 4 - to add together to make eg. 36


In that example the answer is yes.  5+8+23 make 36.
1, 9, 14 and 4 are not needed
zzynxSr. Software engineer
CERTIFIED EXPERT

Commented:
>> 2+4+8 is 14 which is not equal to 10 so above should be false right?
Not right. 2+8 = 10 so return true.
The challenge wants you to look for sub sets too.
ste5anSenior Developer
CERTIFIED EXPERT

Commented:
As I said:  you have a input set and you're looking for a sub-set which fulfills a certain condition.

The groupSum() function should return true if at least one of all possible sub-sets fulfill your condition.

Read the links I've provided. This test is about implementing a function on a unordered set of numbers.

In the case of groupSum(0, [2, 4, 8], 10):

The input set is {2, 4, 8}.
All possible sub-sets are: {}, {2}, {4}, {8}, {2, 4}, {4, 8}, {2, 8}, {2, 4, 8}

In the case of groupSum(0, [1, 3 , 4,  2], 4):
All possible sub-sets are: {}, {1}, {3}, {4}, {2}, {1, 3}, {1, 4}, {1, 2}, {3, 4}, {3, 2}, {4 ,2}, {1, 3, 4}, {1, 3, 2}, {1, 4, 2}, {3, 4, 2}, {1, 3, 4, 2},
nociSoftware Engineer
CERTIFIED EXPERT
Distinguished Expert 2019

Commented:
@sarabande, you should not give the solution to the whole problem....
schoolwork like question.
CERTIFIED EXPERT
Top Expert 2016

Commented:
schoolwork like question.

you may look at gudii9's history. actually his questions are not of academic nature as far as i can judge.

you may have recognized that the problem is not simple and that the pseudo code i have given still seems to be not sufficient to derive valid code from it.

Sara
nociSoftware Engineer
CERTIFIED EXPERT
Distinguished Expert 2019

Commented:
Q was about clarification of the challenge...

Challenge makes me think it is a game or thought provoker type of simple questions.
I have seen more of the Q's from him.
i think he needs to get more analythical about  reading the excersizes.

Author

Commented:
so any combination any subset of numbers sum must be same as target value if yes return true other wise return false right?



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

Open in new window



can you please elaborate on above 3 cases?

if (start >= nums.length) { // first deal with the corner case
     return (target == 0);

target is already given input argument right?
why are we comparing it with 0?
AndyAinscowFreelance programmer / Consultant
CERTIFIED EXPERT

Commented:
>>target is already given input argument right?

Correct.  Do you know what recursion is?
zzynxSr. Software engineer
CERTIFIED EXPERT

Commented:
>>target is already given input argument right?
Indeed. As can be seen in the method's argument list:
public boolean groupSum(int start, int[] nums, int target) {
}

Open in new window


>> why are we comparing it with 0?
Well, if you should start your search at a place where there is nothing to find, this can only lead to a match if the given target value was 0.
So, assume your array only has eg. 3 element (at indices 0, 1 and 2) and start = 3 (or higher), then you should only return true if the target value was 0.
CERTIFIED EXPERT
Top Expert 2016

Commented:
>> why are we comparing it with 0?
in the initial call the target argument is the sum which we should try to build by using one or more elements of the array and sum them up.

in the function there are two recursive calls with start index incremented by 1. with the first of these recursive calls we want to handle the case where the current element at nums[start] was included into the subset, while the second call handles the case where the current element was not in the subset. for the first case we subtract the current value from target since the remaining elements now only have to sum up to (target - nums[start]) in case the current value already is included.

that way the target always would become smaller (granted we have only positive values) if we go the first branch and remains equal if we use the second branch. if target was 0 we have the case that all the values that have been substracted from original target in the stack calls exactly sum up to the initial target. therefore, we can return with true.

Sara
AndyAinscowFreelance programmer / Consultant
CERTIFIED EXPERT

Commented:
gudii9, do you know what recursion in general is?  If yes then do you know what backtracking recursion is?

Author

Commented:
backtracking recursion is not clear to me. Recursion i got familiar with last few challenges. How backtracking recursion is different from recursion?
rrzstudent
CERTIFIED EXPERT
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
rrzstudent
CERTIFIED EXPERT
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
current sum is 0
 at index 0 add 11 current sum is 11
 at index 1 add 2 current sum is 13
 at index 2 add 3 current sum is 16
 at index 3 add 4 current sum is 20
 at index 4 add 8 current sum is 28

clear till above. understanding further
rrzstudent
CERTIFIED EXPERT
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
CERTIFIED EXPERT
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
CERTIFIED EXPERT
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
rrzstudent
CERTIFIED EXPERT
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
go back to the last "branching" and choose the other branch. this is exactly the point where we speak of "backtracking".

not clear on last branching?
please advise

Author

Commented:
visualized like if you would iterate a tree where you start at the root, then go the first branch, then to the first branch of this branch, and so on. finally you are at the end and have to go back to the last "branching" and choose the other branch. this is exactly the point where we speak of "backtracking".

not clear on iterate tree part. what it means?
is it like climbing a tree?
or iterating a TreeMap?

please elaborate may be with a picture

Author

Commented:
so backtracking recursion is algorithem where as recursion is just a method?

Author

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

above diagram is more clear in terms of tree and leaf concept

Starting at Root, your options are A and B. You choose A.
At A, your options are C and D. You choose C.
C is bad. Go back to A.
At A, you have already tried C, and it failed. Try D.
D is bad. Go back to A.
At A, you have no options left to try. Go back to Root.
At Root, you have already tried A. Try B.
At B, your options are E and F. Try E.
E is good. Congratulations!

Author

Commented:
Starting at Root, your options are A and B. You choose A.
At A, your options are C and D. You choose C.
C is bad. Go back to A.
At A, you have already tried C, and it failed. Try D.
D is bad. Go back to A.
At A, you have no options left to try. Go back to Root.
At Root, you have already tried A. Try B.
At B, your options are E and F. Try E.
E is good. Congratulations!
In this example we drew a picture of a tree. The tree is an abstract model of the possible sequences of choices we could make. There is also a data structure called a tree, but usually we don't have a data structure to tell us what choices we have. (If we do have an actual tree data structure, backtracking on it is called depth-first tree searching.)


The backtracking algorithm.

Here is the algorithm (in pseudocode) for doing backtracking from a given node n:

boolean solve(Node n) {
    if n is a leaf node {
        if the leaf is a goal node, return true
        else return false
    } else {
        for each child c of n {
            if solve(c) succeeds, return true
        }
        return false
    }
}

i understand the diagram and explanation. But not clear on the psedoc code


what is C and what is N in psedo code? please advise

Author

Commented:
public class Sum2 {
    public static int targetSum = 10;
    public static int[] nums = new int[]{3, 2, 4, 8};
	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) {
		System.out.println(" current sum is " + (targetSum - target));
		if(start >= nums.length) { 
			if(target == 0){return true;}
			else{
				System.out.print(" backtrack ");
				return false;
			}
		}
		System.out.print(" at index " + start + " add " + nums[start]);
		if(groupSum(start + 1, nums, target - nums[start])) { 
			return true;
		}
		System.out.println(" don't include index " + start);
		if(groupSum(start + 1, nums, target)) { 
			return true;
		}
		return false;
	}
}

Open in new window


for above program what is the root node what is the leaf and how we are back tracking? i am bit unclear on above approach.

i got clarity on console output now

 current sum is 0
 at index 0 add 3 current sum is 3
 at index 1 add 2 current sum is 5
 at index 2 add 4 current sum is 9
 at index 3 add 8 current sum is 17
 backtrack  don't include index 3
 current sum is 9
 backtrack  don't include index 2
 current sum is 5
 at index 3 add 8 current sum is 13
 backtrack  don't include index 3
 current sum is 5
 backtrack  don't include index 1
 current sum is 3
 at index 2 add 4 current sum is 7
 at index 3 add 8 current sum is 15
 backtrack  don't include index 3
 current sum is 7
 backtrack  don't include index 2
 current sum is 3
 at index 3 add 8 current sum is 11
 backtrack  don't include index 3
 current sum is 3
 backtrack  don't include index 0
 current sum is 0
 at index 1 add 2 current sum is 2
 at index 2 add 4 current sum is 6
 at index 3 add 8 current sum is 14
 backtrack  don't include index 3
 current sum is 6
 backtrack  don't include index 2
 current sum is 2
 at index 3 add 8 current sum is 10
 ======>Found group sum to 10? true

Author

Commented:
if(groupSum(start + 1, nums, target - nums[start])) { 

Open in new window


why we have two different if conditions as above and as below without - nums[start])

if(groupSum(start + 1, nums, target)) {
please advise
rrzstudent
CERTIFIED EXPERT
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
i am not able to come up with pseudo code for these back track recursion problems as they are bit complex compared to all other coding bat challenge topics. can you post sample pseudo code for this challenge on how to proceed?

Author

Commented:
may be small diagram helps me to understand this challenge better with leaf and node , child nodes with result true or false etc?
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
rrzstudent
CERTIFIED EXPERT
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
CERTIFIED EXPERT

Commented:
As should be evident now, backtracking, whether recursive or not, is a whole topic in itself. By going through a number of examples, it may start to sink in.

The problem, I think, in learning about backtracking, is that it takes an animation to get the feel of it. The printouts from the code attempt to provide that, but as with all printouts, it is hard to visualize the graphical aspects that are often associated with backtracking examples. By observing a number of animated examples, then you begin to get the sense of what the pseudo-code might look like.

If you want to pursue this backtracking question in this thread, then you should request a number of online videos to watch.

Author

Commented:
If you want to pursue this backtracking question in this thread, then you should request a number of online videos to watch.

can you please provide online videos links
rrzstudent
CERTIFIED EXPERT

Commented:
All you have to do is search on youtube.
https://www.youtube.com/results?search_query=backtrack+recursion

Author

Commented:
will check that. let me digest the pseudo code and code as well
rrzstudent
CERTIFIED EXPERT

Commented:
Please share with us which video that you found most useful.

Author

Commented:
sure

Author

Commented:
Here is my attempt at pseudo code.  
groupSum(){
 if(we stepped through the whole array
     and the sum of the elements that we selected is equal to target) then return true
 otherwise
i got above

otherwise
 if(a call to groupSum after
    adding current element of the array to the current sum
    and stepping to next element returns true) then return true  
  otherwise
  if(a call to groupSum after
     stepping to next element returns true) then return true  
  otherwise return false

above is not that clear.
above two looks same to me?
rrzstudent
CERTIFIED EXPERT

Commented:
above two looks same to me?
The first one adds the current element to the sum. The second one does not.

Author

Commented:
oh i see. let me think

Author

Commented:
The first one adds the current element to the sum. The second one does not

why adds for first and not for second. please advise

Author

Commented:
once i know this clearly,  i think other 9 challenges are almost similar i believe
rrzstudent
CERTIFIED EXPERT

Commented:
why adds for first and not for second. please advise
 Let's look at the code. The recursion
groupSum(start + 1, nums, target - nums[start])

Open in new window

adds nums[start] to the current sum by making its call with a target parameter which is nums[start] less than it was before. The base case is the condition target == 0  (and where the array was stepped through to the end)
I chose my print statement as
System.out.println(" current sum is " + (targetSum - target));

Open in new window

Therefore when target == 0  we have current sum equal to targetSum .  
The other recursion
(groupSum(start + 1, nums, target)

Open in new window

passes the same target value to the next call. The value of the current array element is not added to the current sum.  
The difference between this challenge and other recursion challenges in the your past questions is the fact the recursive calls here are wrapped in a "if" statement. This allows the execution to keep searching all the possibilities even after a false was returned.

Author

Commented:
i am still thinking

public 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


in above solution
within base case how we assumed target is always non zero to return false all the time?
there are case where target is zero and also non zero right?
if start is greater than equal to array length we are assuming as true always right like below

groupSum(1, [9], 0) → true      true      OK

Author

Commented:
public class Sum2 {
    public static int targetSum = 10;
    public static int[] nums = new int[]{3, 2, 4, 8};
	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


while debugging above

index--- target
1  ----7
2------5
3------1
4-----(-7)
then as 4>=4 so it went to the first if loop right which should have return false as
-7 == 0 is false and hence method should exit right. i have not understood how debugger is still running later as well
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
later it went into below if

  if (groupSum(start + 1, nums, target)) {
                  return true;
              }

with start as 4 and target as 1 not sure what is 1 means?
targetOne.png
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
i am clear until

1  ----7
2------5
3------1


then what happened next
not clear on below cases ??
4----->-7 case and what happened further more? i was not clear??

Author

Commented:
no, it can't return false as long as negative numbers are allowed in the set. if so, target -7 could turn to 0 by subtracting -7 or by subtracting -3 and -4.
we only have array here right not set?? please elaborate

Author

Commented:
return -7==0

then what supposed to happen. is above returns true or false??
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
therefore it returned false (and stopped recusion for this branch) because target == -7 what is not 0

i see.

-7==0 is false so this branch stopped for recursion.

then how new branch starts? where is new branch. may be can you elaborate with a picture about next and subsequent branches. total how many branches we have like this to recurse??
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
it proceeds with a second recursive call where the old target was not changed. thi second call would open a new "branch" which doesn't take the current array number into account what means that if this (second) branch leads to a solution set for the challenge, the current number would not be contained in the set.


index--- target
1  ----7
2------5
3------1
4-----(-7)//is this is second branch??

Author

Commented:
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 changed inputs as above to avoid confusion between index and the input numbers
rrzstudent
CERTIFIED EXPERT
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
the second branch is 4-----(1) what means that the 8 was skipped.
why 8 skipped at second branch?
on second branch are we moving from left to right or right to left?
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
Let me think

Author

Commented:
focussing on ID: 41846057 to understand console output

Author

Commented:
i like below explanation looking for some graphical representation as below

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

Author

Commented:
http://www.dreamincode.net/forums/topic/258287-a-look-at-backtracking/
looking at above link which says undo all changes before moving to next branch

Author

Commented:
rereading thread all over again to hope to get solid understanding on this backward recursion which keeps my mind busy for many weeks

# a41841338

So, from where you left off
...
 at index 4 add 8 current sum is 28
 backtrack
 current sum is 20
 backtrack
 current sum is 16 (this time we will not include index 3(which has a value of 4))

not clear why we skipped index 3 while backtracing

what do you mean which has a value of 4??

Author

Commented:

In the case of groupSum(0, [2, 4, 8], 10):

The input set is {2, 4, 8}.
All possible sub-sets are: {}, {2}, {4}, {8}, {2, 4}, {4, 8}, {2, 8}, {2, 4, 8}

In the case of groupSum(0, [1, 3 , 4,  2], 4):
All possible sub-sets are: {}, {1}, {3}, {4}, {2}, {1, 3}, {1, 4}, {1, 2}, {3, 4}, {3, 2}, {4 ,2}, {1, 3, 4}, {1, 3, 2}, {1, 4, 2}, {3, 4, 2}, {1, 3, 4, 2},

now i understand recurion what it is. but not clearly understood how backward recursion works in real time?? esp my challenge solution is not yet clear in terms of flow callign function in if loop and adding once not adding other time. everything looks disconnected pieces to me? please advise

Author

Commented:
Here is my attempt at pseudo code.  
groupSum(){
 if(we stepped through the whole array
     and the sum of the elements that we selected is equal to target) then return true
 otherwise
 if(a call to groupSum after
    adding current element of the array to the current sum
    and stepping to next element returns true) then return true  
  otherwise
  if(a call to groupSum after
     stepping to next element returns true) then return true  
  otherwise return false
 
}

trying to understand above pseudo code

Author

Commented:
if(a call to groupSum after
    adding current element of the array to the current sum
    and stepping to next element returns true) then return true  
  otherwise
  if(a call to groupSum after
     stepping to next element returns true) then return true  
  otherwise return false
 
}

what is stepping what is adding??to what we are stepping and we are adding?

Author

Commented:
public boolean groupSum(int start, int[] nums, int target) {
  // Base case: if there are no numbers left, then there is a
  // solution only if target is 0.
  if (start >= nums.length) return (target == 0);
 
  // Key idea: nums[start] is chosen or it is not.
  // Deal with nums[start], letting recursion
  // deal with all the rest of the array.
 
  // Recursive call trying the case that nums[start] is chosen --
  // subtract it from target in the call.
  if (groupSum(start + 1, nums, target - nums[start])) return true;
 
  // Recursive call trying the case that nums[start] is not chosen.
  if (groupSum(start + 1, nums, target)) return true;
 
  // If neither of the above worked, it's not possible.
  return false;
}

what is difference between chosen and not chosen case??

Author

Commented:
 // Recursive call trying the case that nums[start] is chosen --
  // subtract it from target in the call.
  if (groupSum(start + 1, nums, target - nums[start])) return true;

if it is nums[start] chosen why we are subtracting?? not clear?

 // Recursive call trying the case that nums[start] is not chosen.
  if (groupSum(start + 1, nums, target)) return true;

if not choosen why not we are not subtracting?
rrzstudent
CERTIFIED EXPERT
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
start:3 target:6-5==1                    // that is a first recursive call subtracting 5 from the target 6

is above statement should not be as below??

start:3 target:6-5==1                    // that is a third recursive call subtracting 5 from the target 6

after first then second third should come right sequentially?

Author

Commented:
  if (groupSum(start + 1, nums, target - nums[start])) return true;

Open in new window


when does it return true?
does it return true as it finally calls below base case?
if (start >= nums.length) return (target == 0);
  

Open in new window


please advise

Author

Commented:
start:0 target:15                        // that is the initial call
start:1 target:15-9==6                   // that is a first recursive call subtracting 9 from the target 15
start:2 target:6                         // that is a second recursive call at start 2. we don't subtract 7 from target 6
start:3 target:6-5==1                    // that is a first recursive call subtracting 5 from the target 6
start:4 target:1                         // that is a second recursive call at start 4. we don't subtract 3 from target 1
start:5 target:1-1==0                    // that is a first recursive call subtracting 1 from the target 1

Open in new window


this all assuming int start i.e first argument to the method as 0 right?

Author

Commented:
start:0 target:15                        // that is the initial call //for this 3rd if block i.e  if (groupSum(start + 1, nums, target)) return true; block called??
start:1 target:15-9==6                   // that is a first recursive call subtracting 9 from the target 15//for this 2nd if block i.e   if (groupSum(start + 1, nums, target - nums[start])) return true; called??
start:2 target:6                         // that is a second recursive call at start 2. we don't subtract 7 from target 6//for this 3rd if block i.e  if (groupSum(start + 1, nums, target)) return true; block called??
start:3 target:6-5==1                    // that is a first recursive call subtracting 5 from the target 6// that is a first recursive call subtracting 9 from the target 15//for this 2nd if block i.e   if (groupSum(start + 1, nums, target - nums[start])) return true; called??
start:4 target:1                         // that is a second recursive call at start 4. we don't subtract 3 from target 1//for this 3rd if block i.e  if (groupSum(start + 1, nums, target)) return true; block called??
start:5 target:1-1==0                    // that is a first recursive call subtracting 1 from the target 1// that is a first recursive call subtracting 9 from the target 15//for this 2nd if block i.e   if (groupSum(start + 1, nums, target - nums[start])) return true; called??

Open in new window



given code is as below

public boolean groupSum(int start, int[] nums, int target) {
  // Base case: if there are no numbers left, then there is a
  // solution only if target is 0.
  if (start >= nums.length) return (target == 0);
  
  // Key idea: nums[start] is chosen or it is not.
  // Deal with nums[start], letting recursion
  // deal with all the rest of the array.
  
  // Recursive call trying the case that nums[start] is chosen --
  // subtract it from target in the call.
  if (groupSum(start + 1, nums, target - nums[start])) return true;
  
  // Recursive call trying the case that nums[start] is not chosen.
  if (groupSum(start + 1, nums, target)) return true;
  
  // If neither of the above worked, it's not possible.
  return false;
}

Open in new window

Author

Commented:
what is difference between chosen and not chosen case??
When the code subtracts the current element from the target that is when it is chosen. In this code line
groupSum(start + 1, nums, target - nums[start])

Select all
 
Open in new window
nums[start] is the current element of the array.
if it is nums[start] chosen why we are subtracting?? not clear?
We are subtracting nums[start] from target and sending the result as the third parameter in the call to groupSum method. The target is being reduced each time a element is chosen. This is the strategy of recursion. Little by little we work towards the solution.

how we are reaching to base case finally in both above cases given base case as below?

  // Base case: if there are no numbers left, then there is a
  // solution only if target is 0.
  if (start >= nums.length) return (target == 0);
rrzstudent
CERTIFIED EXPERT

Commented:
how we are reaching to base case finally in both above cases given base case as below?
 Each  of the recursive calls, either
(groupSum(start + 1, nums, target - nums[start]) 

Open in new window

 or
(groupSum(start + 1, nums, target)

Open in new window

they both increment start and step through the nums array.
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
look into the function. there are two (recursive) calls of groupSum, the first and the second. both calls are calling groupSum with start+1 as first argument.

i see there only two recursive calls here

Author

Commented:
so

if we look at the function when start == 1 and target == 6, you see that the second call would be
groupSum(start+1, target)  what is (start:2, 6)

you mean like below instead

so

if we look at the function when start == 1 and target == 6, you see that the second call would be
groupSum(start+1, target)  what is (start:2, nums, 6)


there should be nums as second argument to this method right?

Author

Commented:
start:0 target:15      // that is from the initial call

what you mean by initial call? first if loop?

Author

Commented:
start:0 target:15      // that is from the initial call

why not as below

start:0 target:6 (i.e 15-9 as 9 is at index 0 thinking start is same as index here??)      // that is from the initial call

Author

Commented:
public boolean groupSum(int start, int[] nums, int target) {
  // Base case: if there are no numbers left, then there is a
  // solution only if target is 0.
  if (start >= nums.length) return (target == 0);
  
  // Key idea: nums[start] is chosen or it is not.
  // Deal with nums[start], letting recursion
  // deal with all the rest of the array.
  
  // Recursive call trying the case that nums[start] is chosen --
  // subtract it from target in the call.
  if (groupSum(start + 1, nums, target - nums[start])) return true;
  
  // Recursive call trying the case that nums[start] is not chosen.
  if (groupSum(start + 1, nums, target)) return true;
  
  // If neither of the above worked, it's not possible.
  return false;
}

Open in new window

not sure why 3 lines of above code is so hard to understand to my brain


every time


 // Recursive call trying the case that nums[start] is chosen --
  // subtract it from target in the call.
  if (groupSum(start + 1, nums, target - nums[start])) return true;

above first recursion call  only made right

when second recusion call get chance?(only after first recursion call as a natural progression?)
CERTIFIED EXPERT

Commented:
you said you would post the video that helped you. which video did you watch?

Author

Commented:
YouTube video
CERTIFIED EXPERT

Commented:
youtube - some are good some are bad post the link that you watched.
i am sure that you bookmarked it.

Author

Commented:
there is no detailed explanation though.

i am still struggling with understanding this challenge from where the flow start how it goes and how it ends with base case for given array
say
0. {9,7.5.3.1},15

i understand now
15-(9+5+1) results zero so skip alternate elements.

but not sure how we are coding for compiler to understand using below 3 lines
  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;
actually 4 lines one more default case as below
  return false;
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
regardless whether they subtracted their own number (first call) or not (second call)
     // we need to go the shortest way back to the initial caller.

is that is reason we are always returning true in first recursion and second recursion calls?

Author

Commented:
public class Sum2 {
    public static int targetSum = 15;
    public static int[] nums = new int[]{9, 7, 5, 3,1};
	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) {
		//System.out.println(" current sum is " + (targetSum - target)+" just before base case call");
	//	System.out.println("---> just before base case call");
		if(start >= nums.length) { 
			if(target == 0){return true;}
			else{
				System.out.println(" backtrack from base case ");
				return false;
			}
		}
		System.out.println(" at index " + start + " add " + nums[start]+" just before frirsr recursion call");
		if(groupSum(start + 1, nums, target - nums[start])) { 
			return true;
		}
		System.out.println(" don't include index " + start+" just before second recursion call");
		if(groupSum(start + 1, nums, target)) { 
			return true;
		}
		return false;
	}
}

Open in new window


 at index 0 add 9 just before frirsr recursion call
 at index 1 add 7 just before frirsr recursion call
 at index 2 add 5 just before frirsr recursion call
 at index 3 add 3 just before frirsr recursion call
 at index 4 add 1 just before frirsr recursion call
 backtrack from base case
 don't include index 4 just before second recursion call
 backtrack from base case
 don't include index 3 just before second recursion call
 at index 4 add 1 just before frirsr recursion call
 backtrack from base case
 don't include index 4 just before second recursion call
 backtrack from base case
 don't include index 2 just before second recursion call
 at index 3 add 3 just before frirsr recursion call
 at index 4 add 1 just before frirsr recursion call
 backtrack from base case
 don't include index 4 just before second recursion call
 backtrack from base case
 don't include index 3 just before second recursion call
 at index 4 add 1 just before frirsr recursion call
 backtrack from base case
 don't include index 4 just before second recursion call
 backtrack from base case
 don't include index 1 just before second recursion call
 at index 2 add 5 just before frirsr recursion call
 at index 3 add 3 just before frirsr recursion call
 at index 4 add 1 just before frirsr recursion call
 backtrack from base case
 don't include index 4 just before second recursion call
 backtrack from base case
 don't include index 3 just before second recursion call
 at index 4 add 1 just before frirsr recursion call
 ======>Found group sum to 15? true


trying debugging parallelly on eclipse and got above output. checking that as well

Author

Commented:
public class Sum2 {
    public static int targetSum = 15;
    public static int[] nums = new int[]{9, 7, 5, 3,1};
	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) {
		//System.out.println(" current sum is " + (targetSum - target)+" just before base case call");
	//	System.out.println("---> just before base case call");
		if(start >= nums.length) { 
			if(target == 0){return true;}
			else{
				System.out.println(" @@@@else loop of base case as start is not greater than nums.length ");
				return false;
			}
		}
		System.out.println(" ***at index " + start + " subtract " + nums[start]+" just before first recursion call"+"  target - nums[start] is "+(target - nums[start]));
		if(groupSum(start + 1, nums, target - nums[start])) { 
			return true;
		}
		System.out.println(" ----->don't include index and do not choose to subtract nums[start]  " + start+" just before second recursion call");
		if(groupSum(start + 1, nums, target)) { 
			return true;
		}
		return false;
	}
}

Open in new window


 ***at index 0 subtract 9 just before first recursion call  target - nums[start] is 6
 ***at index 1 subtract 7 just before first recursion call  target - nums[start] is -1
 ***at index 2 subtract 5 just before first recursion call  target - nums[start] is -6
 ***at index 3 subtract 3 just before first recursion call  target - nums[start] is -9
 ***at index 4 subtract 1 just before first recursion call  target - nums[start] is -10
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at index 4 subtract 1 just before first recursion call  target - nums[start] is -7
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  2 just before second recursion call
 ***at index 3 subtract 3 just before first recursion call  target - nums[start] is -4
 ***at index 4 subtract 1 just before first recursion call  target - nums[start] is -5
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at index 4 subtract 1 just before first recursion call  target - nums[start] is -2
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  1 just before second recursion call
 ***at index 2 subtract 5 just before first recursion call  target - nums[start] is 1
 ***at index 3 subtract 3 just before first recursion call  target - nums[start] is -2
 ***at index 4 subtract 1 just before first recursion call  target - nums[start] is -3
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at index 4 subtract 1 just before first recursion call  target - nums[start] is 0
 ======>Found group sum to 15? true


i made more meaningful sysouts here
CERTIFIED EXPERT

Commented:
The youtube video link you showed was code-oriented, boring, and as you said, doesn't go into detail. So, you should have moved onto other videos. I see over 50 videos, and have seen some that could possibly help you understand this question in just a couple of hours.
I have not understand above description. please advise

Going through pseudo-code first is not the approach I have seen in online courses. First they explain the problem. Then they explain a method using pictures. Then they show some pseudo code and talk about complexity.

Why spend almost 2 months on understanding the problem description, when just a couple hours of finding the right set of videos is all you need.

Just go to youtube, and search on subset sum.

Author

Commented:
public class Sum2 {
    public static int targetSum = 15;
    public static int[] nums = new int[]{9, 7, 5, 3,1};
	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) {
		//System.out.println(" current sum is " + (targetSum - target)+" just before base case call");
	//System.out.println("---> just before base case call");
		if(start >= nums.length) { 
			if(target == 0){return true;}
			else{
				System.out.println(" @@@@else loop of base case as start is not greater than nums.length ");
				return false;
			}
		}
		System.out.println(" ***at start value which evenually index for nums array " + start + " subtract " + nums[start]+" just before first recursion call"+" difference of  target - nums[start] is "+(target - nums[start]));
		if(groupSum(start + 1, nums, target - nums[start])) { 
			return true;
		}
		System.out.println(" ----->don't include index and do not choose to subtract nums[start]  " + start+" just before second recursion call");
		if(groupSum(start + 1, nums, target)) { 
			return true;
		}
		return false;
	}
}

Open in new window


further modified sysouts
 ***at start value which evenually index for nums array 0 subtract 9 just before first recursion call difference of  target - nums[start] is 6
 ***at start value which evenually index for nums array 1 subtract 7 just before first recursion call difference of  target - nums[start] is -1
 ***at start value which evenually index for nums array 2 subtract 5 just before first recursion call difference of  target - nums[start] is -6
 ***at start value which evenually index for nums array 3 subtract 3 just before first recursion call difference of  target - nums[start] is -9
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -10
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -7
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  2 just before second recursion call
 ***at start value which evenually index for nums array 3 subtract 3 just before first recursion call difference of  target - nums[start] is -4
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -5
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -2
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  1 just before second recursion call
 ***at start value which evenually index for nums array 2 subtract 5 just before first recursion call difference of  target - nums[start] is 1
 ***at start value which evenually index for nums array 3 subtract 3 just before first recursion call difference of  target - nums[start] is -2
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -3
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is 0
 ======>Found group sum to 15? true

Author

Commented:
Why spend almost 2 months on understanding the problem description, when just a couple hours of finding the right set of videos is all you need.

Just go to youtube, and search on subset sum.
can you please point to some good videos on this. i am new to this topic

Author

Commented:
public class Sum2 {
    public static int targetSum = 15;
    public static int[] nums = new int[]{9, 7, 5, 3,1};
	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) {
		//System.out.println(" current sum is " + (targetSum - target)+" just before base case call");
	//System.out.println("---> just before base case call");
		if(start >= nums.length) { 
			if(target == 0){return true;}
			else{
				System.out.println(" @@@@else loop of base case as start is not greater than nums.length ie backtracking ");
				return false;
			}
		}
		System.out.println(" ***at start value which evenually index for nums array " + start + " subtract " + nums[start]+" just before first recursion call"+" difference of  target - nums[start] is "+(target - nums[start]));
		if(groupSum(start + 1, nums, target - nums[start])) { 
			return true;
		}
		System.out.println(" ----->don't include index and do not choose to subtract nums[start]  " + start+" just before second recursion call");
		if(groupSum(start + 1, nums, target)) { 
			return true;
		}
		return false;
	}
}

Open in new window


changed few other sysouts

 ***at start value which evenually index for nums array 0 subtract 9 just before first recursion call difference of  target - nums[start] is 6
 ***at start value which evenually index for nums array 1 subtract 7 just before first recursion call difference of  target - nums[start] is -1
 ***at start value which evenually index for nums array 2 subtract 5 just before first recursion call difference of  target - nums[start] is -6
 ***at start value which evenually index for nums array 3 subtract 3 just before first recursion call difference of  target - nums[start] is -9
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -10
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -7
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  2 just before second recursion call
 ***at start value which evenually index for nums array 3 subtract 3 just before first recursion call difference of  target - nums[start] is -4
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -5
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -2
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  1 just before second recursion call
 ***at start value which evenually index for nums array 2 subtract 5 just before first recursion call difference of  target - nums[start] is 1
 ***at start value which evenually index for nums array 3 subtract 3 just before first recursion call difference of  target - nums[start] is -2
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -3
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is 0
 ======>Found group sum to 15? true

Author

Commented:
public class Sum2 {
    public static int targetSum = 15;
    public static int[] nums = new int[]{9, 7, 5, 3,1};
	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) {
		//System.out.println(" current sum is " + (targetSum - target)+" just before base case call");
	//System.out.println("---> just before base case call");
		if(start >= nums.length) { 
			if(target == 0){return true;}
			else{
				System.out.println(" @@@@else loop of base case as start is not greater than nums.length ie backtracking ");
				return false;
			}
		}
		System.out.println(" ***at start value which evenually index for nums array " + start + " subtract " + nums[start]+" just before first recursion call"+" difference of  target - nums[start] is "+(target - nums[start]));
		if(groupSum(start + 1, nums, target - nums[start])) { 
			System.out.println("recursion call 1");
			return true;
		}
		System.out.println(" ----->don't include index and do not choose to subtract nums[start]  " + start+" just before second recursion call");
		if(groupSum(start + 1, nums, target)) { 
			System.out.println("recursion call 2");
			return true;
		}
		return false;
	}
}

Open in new window


modified sysouts

 ***at start value which evenually index for nums array 0 subtract 9 just before first recursion call difference of  target - nums[start] is 6
 ***at start value which evenually index for nums array 1 subtract 7 just before first recursion call difference of  target - nums[start] is -1
 ***at start value which evenually index for nums array 2 subtract 5 just before first recursion call difference of  target - nums[start] is -6
 ***at start value which evenually index for nums array 3 subtract 3 just before first recursion call difference of  target - nums[start] is -9
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -10
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -7
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  2 just before second recursion call
 ***at start value which evenually index for nums array 3 subtract 3 just before first recursion call difference of  target - nums[start] is -4
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -5
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -2
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  1 just before second recursion call
 ***at start value which evenually index for nums array 2 subtract 5 just before first recursion call difference of  target - nums[start] is 1
 ***at start value which evenually index for nums array 3 subtract 3 just before first recursion call difference of  target - nums[start] is -2
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is -3
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 1 just before first recursion call difference of  target - nums[start] is 0
recursion call 1
recursion call 2
recursion call 1
recursion call 2
recursion call 1
 ======>Found group sum to 15? true
CERTIFIED EXPERT

Commented:
I looked at a couple on the first page and there were two different ways to solve the problem.
There's one with 51 videos in the playlist (from various sources).

It is better for you to take your time and go through some of them yourself in order to hear different ways of understanding the problem.

Author

Commented:
I looked at a couple on the first page and there were two different ways to solve the problem.
There's one with 51 videos in the playlist (from various sources).

which playlist you are referring. i might have missed it earlier?

Author

Commented:
public class Sum2 {
    public static int targetSum = 10;
    public static int[] nums = new int[]{11, 2, 3, 4, 8};
	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) {
		//System.out.println(" current sum is " + (targetSum - target)+" just before base case call");
	//System.out.println("---> just before base case call");
		if(start >= nums.length) { 
			if(target == 0){return true;}
			else{
				System.out.println(" @@@@else loop of base case as start is not greater than nums.length ie backtracking ");
				return false;
			}
		}
		System.out.println(" ***at start value which evenually index for nums array " + start + " subtract " + nums[start]+" just before first recursion call"+" difference of  target - nums[start] is "+(target - nums[start]));
		if(groupSum(start + 1, nums, target - nums[start])) { 
			System.out.println("recursion call 1");
			return true;
		}
		System.out.println(" ----->don't include index and do not choose to subtract nums[start]  " + start+" just before second recursion call");
		if(groupSum(start + 1, nums, target)) { 
			System.out.println("recursion call 2");
			return true;
		}
		return false;
	}
}

Open in new window

with other outputs

 ***at start value which evenually index for nums array 0 subtract 11 just before first recursion call difference of  target - nums[start] is -1
 ***at start value which evenually index for nums array 1 subtract 2 just before first recursion call difference of  target - nums[start] is -3
 ***at start value which evenually index for nums array 2 subtract 3 just before first recursion call difference of  target - nums[start] is -6
 ***at start value which evenually index for nums array 3 subtract 4 just before first recursion call difference of  target - nums[start] is -10
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is -18
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is -14
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  2 just before second recursion call
 ***at start value which evenually index for nums array 3 subtract 4 just before first recursion call difference of  target - nums[start] is -7
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is -15
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is -11
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  1 just before second recursion call
 ***at start value which evenually index for nums array 2 subtract 3 just before first recursion call difference of  target - nums[start] is -4
 ***at start value which evenually index for nums array 3 subtract 4 just before first recursion call difference of  target - nums[start] is -8
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is -16
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is -12
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  2 just before second recursion call
 ***at start value which evenually index for nums array 3 subtract 4 just before first recursion call difference of  target - nums[start] is -5
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is -13
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is -9
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  0 just before second recursion call
 ***at start value which evenually index for nums array 1 subtract 2 just before first recursion call difference of  target - nums[start] is 8
 ***at start value which evenually index for nums array 2 subtract 3 just before first recursion call difference of  target - nums[start] is 5
 ***at start value which evenually index for nums array 3 subtract 4 just before first recursion call difference of  target - nums[start] is 1
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is -7
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is -3
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  2 just before second recursion call
 ***at start value which evenually index for nums array 3 subtract 4 just before first recursion call difference of  target - nums[start] is 4
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is -4
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  4 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  3 just before second recursion call
 ***at start value which evenually index for nums array 4 subtract 8 just before first recursion call difference of  target - nums[start] is 0
recursion call 1
recursion call 2
recursion call 2
recursion call 1
recursion call 2
 ======>Found group sum to 10? true



just to sync up with @rrz cooment earlier
clear till above. understanding further
What do you mean?  Index 4 is the last element of the array.  In the next call to the groupSum method,  start will be equal to 5 which is equal to nums.length .  So the conditional  
(start >= nums.length)  
is true. Since target is equal to 28 (and the conditional target == 0 is false) , the execution backtracks.
So, from where you left off
...
 at index 4 add 8 current sum is 28
 backtrack
 current sum is 20
 backtrack
 current sum is 16 (this time we will not include index 3(which has a value of 4))
 at index 4 add 8 current sum is 24
 backtrack
 current sum is 16
 backtrack
 current sum is 13(this time we will not include index 2(which has a value of 3))
 at index 3 add 4 current sum is 17
 at index 4 add 8 current sum is 25
 backtrack
and so forth.

Author

Commented:
still hard to digest the flow
CERTIFIED EXPERT
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
51 videos in this playlist
https://www.youtube.com/watch?v=5td2QH-x5ck&list=PLsgBj9JKV2vNbXpp8iyyAQnPN7KKtbSIt&index=1

i watched one yesterday. still need to watch more today

Author

Commented:
are you able to find out which of the above "forward" steps are first recursion and which are second recursion?
yes. i am able to find. still not able to figure out complete picture. may be can you please explain with array if just 2 elements say {7,9} with start at 0 and target 9

now it supposed to return true
public class Sum2 {
    public static int targetSum = 9;
    public static int[] nums = new int[]{7,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) {
		//System.out.println(" current sum is " + (targetSum - target)+" just before base case call");
	//System.out.println("---> just before base case call");
		if(start >= nums.length) { 
			if(target == 0){return true;}
			else{
				System.out.println(" @@@@else loop of base case as start is not greater than nums.length ie backtracking ");
				return false;
			}
		}
		System.out.println(" ***at start value which evenually index for nums array " + start + " subtract " + nums[start]+" just before first recursion call"+" difference of  target - nums[start] is "+(target - nums[start]));
		if(groupSum(start + 1, nums, target - nums[start])) { 
			System.out.println("recursion call 1");
			return true;
		}
		System.out.println(" ----->don't include index and do not choose to subtract nums[start]  " + start+" just before second recursion call");
		if(groupSum(start + 1, nums, target)) { 
			System.out.println("recursion call 2");
			return true;
		}
		return false;
	}
}

Open in new window


 ***at start value which evenually index for nums array 0 subtract 7 just before first recursion call difference of  target - nums[start] is 2
 ***at start value which evenually index for nums array 1 subtract 9 just before first recursion call difference of  target - nums[start] is -7
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  1 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  0 just before second recursion call
 ***at start value which evenually index for nums array 1 subtract 9 just before first recursion call difference of  target - nums[start] is 0
recursion call 1
recursion call 2
 ======>Found group sum to 9? true

Author

Commented:
***at start value which evenually index for nums array 0 subtract 7 just before first recursion call difference of  target - nums[start] is 2
 ***at start value which evenually index for nums array 1 subtract 9 just before first recursion call difference of  target - nums[start] is -7

i got forward part 100%


not below backward part later on  which seems more haphazard rather regular orderly flow or movement

@@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  1 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  0 just before second recursion call
 ***at start value which evenually index for nums array 1 subtract 9 just before first recursion call difference of  target - nums[start] is 0
recursion call 1
recursion call 2
 ======>Found group sum to 9? true

Author

Commented:
public class Sum2 {
    public static int targetSum = 9;
    public static int[] nums = new int[]{7,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) {
		//System.out.println(" current sum is " + (targetSum - target)+" just before base case call");
	//System.out.println("---> just before base case call");
		if(start >= nums.length) { 
			if(target == 0){
				System.out.println("inside if base base==========");return true;}
			else{
				System.out.println(" @@@@else loop of base case as start is not greater than nums.length ie backtracking ");
				return false;
			}
		}
		System.out.println(" ***at start value which evenually index for nums array " + start + " subtract " + nums[start]+" just before first recursion call"+" difference of  target - nums[start] is "+(target - nums[start]));
		if(groupSum(start + 1, nums, target - nums[start])) { 
			System.out.println("recursion call 1");
			return true;
		}
		System.out.println(" ----->don't include index and do not choose to subtract nums[start]  " + start+" just before second recursion call");
		if(groupSum(start + 1, nums, target)) { 
			System.out.println("recursion call 2");
			return true;
		}
		return false;
	}
}

Open in new window


i modified sysouts

 ***at start value which evenually index for nums array 0 subtract 7 just before first recursion call difference of  target - nums[start] is 2
 ***at start value which evenually index for nums array 1 subtract 9 just before first recursion call difference of  target - nums[start] is -7
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  1 just before second recursion call
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 ----->don't include index and do not choose to subtract nums[start]  0 just before second recursion call
 ***at start value which evenually index for nums array 1 subtract 9 just before first recursion call difference of  target - nums[start] is 0
inside if base base==========
recursion call 1
recursion call 2
 ======>Found group sum to 9? true
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
3. (s:2, t:-7) you are at length of array and decide to return false since -7 is not equal 0

4. (s:1, t:2) the return happens to come out at step 2 after first recursive call

how t:-7 in step 3 became t:2 in step 4? please advise

Author

Commented:
1. (s:0, t:9)  you take the 7 with initial call (means you subtract 7 from 9 and next target is 2)
you mean above as below?
1. (s:0, t:9)  you take the 7 with initial first recursive call (means you subtract 7 from 9 and next target is 2)

Author

Commented:
so, you run into the second recursive call where you keep target = 2 (not subtracting 9)

why not subtracting here?
does this means step 4 is same as going back step 2 right? where s:1 t:2

Author

Commented:
1. (s:0, t:9)  you take the 7 with initial call (means you subtract 7 from 9 and next target is 2)
2. (s:1, t:2)  you take the 9 with first recursive call (means you subtract 9 from 2 getting -7 for target)
3. (s:2, t:-7) you are at length of array and
decide to return false since -7 is not equal 0

after above bolded part done how it goes to decide to return false since -7 is not equal part of the code which is base case if??
CERTIFIED EXPERT

Commented:
>> don't know why you make simple things complicated
One of the goals in taking a rigorous algorithms course is to learn how to make complicated things simpler, and to prevent simple things from being made complicated. Since we know that this author has not gone through a series of algorithmic lectures, I cannot understand why you would make this statement. This is a hard subject to jump into without the prerequisite lectures!

It is only simple if you have taken a course in algorithms and have actually done dynamic programming with memoization in a number of lectures that finally leads up to this subset sum problem. I have taken or surveyed a few courses, and they don't start off with pseudo-code. First comes the understanding of the problem statement, which is what this OP is about, and which I believe the author actually does understand by now.

Then the courses go into an analysis phase on solving the problem describing the manual method with a small number of items. And after a few examples, a pattern starts appearing, so now they begin to capture that manual pattern in pseudo code. I do not recall seeing an instructor starting off a lecture with pseudo code in these dynamic programming algorithms. Even if you watch the full lectures (typically 60 minutes each), it is still not simple and doesn't usually become simple (at least for me) unless you do a number of exercises in order to better understand the principles.

So, I am not surprised with the effort it is taking to try to grasp the challenge code without first describing the model used to solve the problem. If the author takes the time to fully understand the models without even be concerned about the pseudo code or Java code, then by his making up his own exercises and solving them manually in a methodical way, thereby fully knowing deeply the model, then the author may be able to write his own pseudo code that maps to the model that he now understands.

In the 51 video list, there are some variations of the model. Some, like the first, determine how to obtain a simple true/false answer. Others ask a deeper question, which is, if the answer is true, then provide the subset of numbers which add up to the target number. Others go a little deeper, which is, if the answer is true, give me all subsets which add up to the target number. I wouldn't be surprised if there were slight variations such as "what is the subset whose sum is maximum, but does not exceed the target number". We see models in these videos that includes a matrix that can be filled out manually, or a binary tree which may require pre-sorting.

The route taken here by everyone is very inefficient in answering this OP. Had we stuck with the OP question, and just the OP question, we could have then advised the author to move on to learning how to manually come up with a true/false answer even if the set had 1000 numbers in it.

But if you continue with this approach, then we should take a pool on how long it will take the author to truly understand the experts' points made in this thread. It will definitely happen, but when??

Author

Commented:
For this challenge putting comments as video file helps clear up things faster if at that is possible

Author

Commented:
When you say initial call you mean call at line 5 right within main method?
CERTIFIED EXPERT
Top Expert 2016

Commented:
Since we know that this author has not gone through a series of algorithmic lectures, I cannot understand why you would make this statement.

sorry phoffric, i don't agree. i made this statement not because I think the algorithm is simple but because i think the author should stop discussing with sysouts like

@@@@else loop of base case as start is not greater than nums.length ie backtracking

which no one understands and lead to nowhere. in my opinion it would need years if we continue to discuss on a base like that. with my last two samples, i tried to back away from the abstract programming code towards to explaining each single step. by posting program outputs not fitting to my last comments discussed, the Author tried to depart from this way.

I don't know whether the videos can help or already helped. perhaps the problem is that the videos didn't match exactly to the challenge and open new questions while not answering all those still open.

Sara
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
not sure, whether i fully understand the question, but the decision to return false is because of the following statements in the code:

if(start >= nums.length) {
     if(target == 0){
         return true;
     }
     else{
         return false;
     }
}

got it. which is called base case right in this case?

Author

Commented:
When you say initial call you mean call at line 5 right within main method?

yes. the function groupSum was initially called from main by passing start==0 and target==9.

so step 1 it should be after right

1. (s:0, t:9)  you take the 7 after initial call (means you subtract 7 from 9 and next target is 2)//as we are taking target 9 with intial call from main method??
2. (s:1, t:2)  you take the 9 with first recursive call (means you subtract 9 from 2 getting -7 for target)
3. (s:2, t:-7) you are at length of array and decide to return false since -7 is not equal 0
4. (s:1, t:2) the return happens to come out at step 2 after first recursive call
    so, you run into the second recursive call where you keep target = 2 (not subtracting 9)
5. (s:2, t:2) again you are at end of array and decide to return false (since 2 is not 0)
6. (s:1, t:2) now you come out after second recursive call which is at end of function, so you return false again
7. (s:0, t:9) you come out after first recursive call for start = 0 and target 9
    so you run into second recursive call with start = 1 and target 9.
8. (s:1, t:9) you take the 9 with first recursive call with start = 2 and target 0 (because the 9 was subtracted now)
9. (s:2, t:0) again you are at end since start = 2 but now target is 0. you return true
10. you come out after first recursive call but as the return was true the if condition is true and you return immediately with true.
11. you come out after second recursive call with true and the if condition is true and you return immediately true.
12. you come out in the initial caller and the challenge result is true.
CERTIFIED EXPERT

Commented:
I don't know why you make simple things complicated

sorry phoffric, i don't agree. i made this statement not because I think the algorithm is simple but because i think the author should stop discussing with sysouts like

 @@@@else loop of base case as start is not greater than nums.length ie backtracking

 which no one understands and lead to nowhere.

This is classic disagreement. If you were in the middle of a jungle in which you were in uncharted territory, but luckily with a transmitter, then you might be asking questions that are leading to nowhere as well. The person on the other end will likely inform you that the questions you are asking are not relevant to the main immediate task, say, of building a fire to keep warm and keep the animals away, until help arrives.

It is obvious why the author is asking questions that you think are complicated. It is because he jumped from coding to complicated algorithms without a gentle transition. Also, with multiple experts trying to help, possibly with different viewpoints on how to learn, it is a credit to the author that he is still persisting with this two month long question.
CERTIFIED EXPERT
Top Expert 2016

Commented:
It is obvious why the author is asking questions that you think are complicated.
is it? i think we come nowhere by arguing among us. i said it is complicated because it was complicated what the author asked me to look over and comment. that is different to the difficulties of the specific learning situation which also may add complexity but is nothing what the author could change by himself.  the point is, that as a teacher i very well may criticise about some specific in order to get a different result back. i think if we would succeed with this challenge, it is because the asker found the recipe to conform to the advisers and not the other way round.

Sara
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
0. main calls groupSum(0, 9)
1. (s:0, t:9)  groupSum calls groupSum(1, 2)  (first recursive call subtracting 7 from 9 getting  2 for target)
2. (s:1, t:2)  groupSum calls groupSum(1, -7) (first recursive call subtracting 9 from 2 getting -7 for target)
3. (s:2, t:-7) length check failed (length >= start): check on target equals 0 failed (target ==-7) ==> return false
4. (s:1, t:2) the return false makes the if statement with first recursive call false ==> no return but step to next statement.
5. (s:1, t:2) groupsSum calls groupSum(2, 2) (second recursive call not subtracting 9 from 2 means: 9 was not taken for sum)
6. (s:2, t:2) length check failed (length >= start): check on target equals 0 failed (target ==2) ==> return false
7. (s:1, t:2) the return false makes the if statement with second recursive call false ==> no return but step to next statement.
8. (s:1, t:2) return false; (next statement after if statement with second recursive call)
9. (s:0, t:9) the return false makes the if statement with first recursive call false ==> no return but step to next statement.
10. (s:0, t:9) groupSum calls groupSum(1, 9) (second recursive call not subtracting 7 from 9 means: 7 was not taken for sum)
11. (s:1, t:9) groupSum calls groupSum(2, 0) (first recursive call subtracting 9 from 9 getting 0 for target)
12. (s:2, t:0) length check failed (length >= start): check on target equals 0 succeeded (target ==0) ==> return true
13. (s:1, t:9) the return true makes the if statement with first recursive call true ==> return true 
14. (s:0, t:9) the return true makes the if statement with second recursive call true ==> return true 
15. main: groupSum(0, 9) returned true and the challenge result is true. 

Open in new window


can you please put above 15 steps as eclipse system out println statements so that when i put break points and debug through eclipse i know exact flow of executionn
public class Sum2 {
    public static int targetSum = 9;
    public static int[] nums = new int[]{7,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) {
		//System.out.println(" current sum is " + (targetSum - target)+" just before base case call");
	//System.out.println("---> just before base case call");
		if(start >= nums.length) { 
			if(target == 0){
				System.out.println("inside if base base==========");return true;}
			else{
				System.out.println(" @@@@else loop of base case as start is not greater than nums.length ie backtracking ");
				return false;
			}
		}
		//System.out.println(" ***at start value which evenually index for nums array " + start + " subtract " + nums[start]+" just before first recursion call"+" difference of  target - nums[start] is "+(target - nums[start]));
		if(groupSum(start + 1, nums, target - nums[start])) { 
			
			System.out.println("recursion call 1 with s value "+(start+1)+"and target "+(target - nums[start]));
			return true;
		}
		//System.out.println(" ----->don't include index and do not choose to subtract nums[start]  " + start+" just before second recursion call");
		if(groupSum(start + 1, nums, target)) { 
			System.out.println("recursion call 2 with s value "+(start+1)+"and target "+(target - nums[start]));
			return true;
		}
		return false;
	}
}

Open in new window

when i changed as above some of steps are eaten by eclipse somehow
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
 @@@@else loop of base case as start is not greater than nums.length ie backtracking
inside if base base==========
recursion call 1 with s value2and target0
recursion call 2 with s value1and target2
 ======>Found group sum to 9? true

Author

Commented:
public boolean groupSum(int start, int[] nums, int target) {
    if (start >= nums.length) return target == 0;
    return groupSum(start + 1, nums, target - nums[start]);
}

Open in new window


why above failed some cases?


Correct for more than half the tests

Your progress graph for this problem

please advise

Author

Commented:
public boolean groupSum(int start, int[] nums, int target) {
    if (start >= nums.length) return target == 0;
   // return groupSum(start + 1, nums, target - nums[start]);
       return groupSum(start + 1, nums, target);
}

Open in new window


why without subtracting case is failing some other?

Expected      Run            
groupSum(0, [2, 4, 8], 10) → true      false      X      
groupSum(0, [2, 4, 8], 14) → true      false      X      
groupSum(0, [2, 4, 8], 9) → false      false      OK      
groupSum(0, [2, 4, 8], 8) → true      false      X      
groupSum(1, [2, 4, 8], 8) → true      false      X      
groupSum(1, [2, 4, 8], 2) → false      false      OK      
groupSum(0, [1], 1) → true      false      X      
groupSum(0, [9], 1) → false      false      OK      
groupSum(1, [9], 0) → true      true      OK      
groupSum(0, [], 0) → true      true      OK      
groupSum(0, [10, 2, 2, 5], 17) → true      false      X      
groupSum(0, [10, 2, 2, 5], 15) → true      false      X      
groupSum(0, [10, 2, 2, 5], 9) → true      false      X      
other tests
X      

why we need subtracting case as well as non subtracting case for this solution???

Author

Commented:
groupSum(0, [9], 1) → false	false	OK	
groupSum(1, [9], 0) → true	true	OK	
groupSum(0, [], 0) → true	true	OK	

Open in new window


how above 8,9 ,10th test cases in results panel pass for both non subtraction as well as subtraction case?

Author

Commented:
public class Sum2 {
    public static int targetSum = 9;
    public static int[] nums = new int[]{7,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) return target == 0;
	    return groupSum(start + 1, nums, t[b]arget - nums[start[/b]]);
	  //return groupSum(start + 1, nums, target);
	}
}

Open in new window


our simple [7,9] array data fails with 'subtraction case' alone

 ======>Found group sum to 9? false

public class Sum2 {
    public static int targetSum = 9;
    public static int[] nums = new int[]{7,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) return target == 0;
	    //return groupSum(start + 1, nums, target - nums[start]);
	     return groupSum(start + 1, nums, [b]target[/b]);
	}
}

Open in new window

it fails 'non subtraction' as well

 ======>Found group sum to 9? false

Author

Commented:
'subtracting case' makes some sense as we are approaching towards base case target value of zero but 'non subtracting case does not make sense to me. why we need 'non subtracting case? please advise

Author

Commented:
what combinations we will miss if i do not take 'non subtraction' case ( i.e  return groupSum(start + 1, nums, target);) apart from 'subtraction case( i.e return groupSum(start + 1, nums, target - nums[start]); )

Author

Commented:
i found below interesting link

http://gregorulm.com/codingbat-java-recursion-2/

I’ll just walk you through the general strategy, using the first exercise as an example: The method “groupSum” takes three arguments. The first, “start”, is the index of an array of integers, the second is the array of integers in question, and the third, “target” is the target value. Now, “start” increases by one with each recursive call. If this value is greater than or equal to the length of the array, then the entire array has been processed. At this point, only the evaluation step has to be done, which consists of checking whether the target value is zero.

i did not get above bolded part.
how evalaution part is relevant for below bolded part of code as we are not subtracting anything to progress towards zero??

public boolean groupSum(int start, int[] nums, int target) {
    if (start >= nums.length) return target == 0;
    return groupSum(start + 1, nums, target - nums[start]);
 //return groupSum(start + 1, nums, target);
}

please advise

Author

Commented:
in the above link i found some explanation like below
I had a similar question so I ended up writing it out to understand.
Heres a simple example to clarify what happens.

nums = {2, 3, 5} // should return true {2, 3} and {5}

two initial calls are made passing the values:
A B
helper(1, nums, 2, 0) || helper(1, nums, 0, 2)

what follows is more calls branching out from those values:
A: helper(2, nums, 5, 0) || helper(2, nums, 2, 3)
B: helper(2, nums, 3, 2) || helper(2, nums, 0, 5)

Each one making more calls that branch out until a final boolean value is returned:
if (start >= nums.length) return sum1 == sum2;

Heres the whole picture: (nums is passed ill just show (start, sum1, sum2) )

helper(0, nums, 0, 0);
/ \
(1, 2, 0) || (1, 0, 2)
/ \ / \
(2, 5, 0) || (2, 2, 3) (2, 3, 2) || (2, 0, 5)
/ \ / \ / \ / \
(3, 10, 0) (3, 5, 5) (3, 7, 3) (3, 2, 8) (3, 8, 2) (3, 3, 7) (3, 5, 5) (3, 0, 10)
F T F F F F T F

Following the calls ends up returning T since each one is an OR.
not clear why author took fourth argument for helper1 and helpter2
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Author

Commented:
package syout;
public class Sum2 {
    public static int step = 0;
    public static int targetSum = 9;
    public static int[] nums = new int[]{7,9};
	public static void main(String args[]) {
        System.out.println("0. main calls groupSum(0, " + targetSum + ")");
        step++;
    }
    public static boolean groupSum(int start, int[] nums, int target) {
        if(start >= nums.length) { 
            step++;
            if(target == 0){
                System.out.println("" + step + ". (s:" + start + ", t:" + target + ") length check failed (length >= start): check on target equals 0 succeded ((target:" + target + " ==> return true"); 
                return true;
            }
            else{
                System.out.println("" + step + ". (s:" + start + ", t:" + target + ") length check failed (length >= start): check on target equals 0 failed (target:" + target + " ==> return false");
                return false;
            }
        }
        step++;
        System.out.println("" + step + ". (s:" + start + ", t:" + target + ") groupSum calls groupSum(" + (start+1) + ", " + (target-nums[start]) + ")  (first recursive call subtracting " + nums[start] + " from " + target + " getting " + (target-nums[start]) + " for target)");
        step++;
        if(groupSum(start + 1, nums, target - nums[start])) { 
            step++;
            System.out.println("" + step + ". (s:" + start + ", t:" + target + ") the return true makes the if statement with first recursive call true ==> return true");
            return true;
        }
        System.out.println("" + step + ". (s:" + start + ", t:" + target + ") the return false makes the if statement with first recursive call false ==> no return but step to next statement.");
        step++;
        System.out.println("" + step + ". (s:" + start + ", t:" + target + ") groupSum calls groupSum(" + (start+1) + ", " + target + ")  (second recursive call not subtracting " + nums[start] + " from " + target + " means " + nums[start] + " was not taken for target)");
        if(groupSum(start + 1, nums, target)) {
            step++;
            System.out.println("" + step + ". (s:" + start + ", t:" + target + ") the return true makes the if statement with second recursive call true ==> return true");
            return true;
        }
        step++;
        System.out.println("" + step + ". (s:" + start + ", t:" + target + ") return false; (next statement after if statement with second recursive call)");
        return false;
    }
}

Open in new window


above gave below output

0. main calls groupSum(0, 9)


not sure why it did not print out other sysouts.

please advise

Author

Commented:
note, i had no environment to test. the code might have typos.

code is not working for me and not printing sysouts except one. can you please advise

Author

Commented:
just prints below

0. main calls groupSum(0, 9)
CERTIFIED EXPERT

Commented:
>> not sure why it did not print out other sysouts.
>> please advise

Whenever lines of code are not executed that you think should be executed, the best advice I can give you is to step through the code in your debugger to see why you are skipping over the code. Using breakpoints judiciously can help speed up the process, but the first time, it doesn't hurt to step through the code and try to understand each line of code while you are doing this.

The next best piece of advice is to let one of the experts either analyze your code and try to figure out what is wrong; or, alternatively, the expert can put the code into their own debugger, and step through the code, and then explain to you which lines of code resulted in your code not executing as you expected.
CERTIFIED EXPERT
Top Expert 2016
Commented:
This problem has been solved!
(Unlock this solution with a 7-day Free Trial)
UNLOCK SOLUTION

Gain unlimited access to on-demand training courses with an Experts Exchange subscription.

Get Access
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Empower Your Career
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE

Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions