Hi,

I am working on below challenge

http://codingbat.com/prob/p145416

I have not understand above description. please advise

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

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

- 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.

I have not understand above description. please adviseif 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

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

Not right. 2+8 = 10 so return true.

The challenge wants you to look for sub sets too.

The groupSum() function should return true

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

In the case of groupSum(0, [1, 3 , 4, 2], 4):

All possible sub-sets are: {}, {1}, {3},

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

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.

Indeed. As can be seen in the method's argument list:

```
public boolean groupSum(int start, int[] nums, int target) {
}
```

>> 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.

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

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.

https://www.youtube.com/results?search_query=backtrack+recursion

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

why adds for first and not for second. please adviseLet's look at the code. The recursion

```
groupSum(start + 1, nums, target - nums[start])
```

adds nums[start] to the current sum by making its call with a target parameter which is nums[start] I chose my print statement as

```
System.out.println(" current sum is " + (targetSum - target));
```

Therefore when target == 0 we have current sum equal to targetSum . The other recursion

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

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.

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])
```

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

they both increment start and step through the nums array.
i am sure that you bookmarked it.

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.

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.

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

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

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.

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

Sara

>> 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.

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

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

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

- Troubleshooting
- Research
- Professional Opinions