CODEWITHSUNDEEP
javaalgorithmrecursive-backtracking
mehmet riza oz
mehmet riza oz

Reputation: 559

what is the algorithm behind the solution below

I encountered recursive exercises for improving my coding skills and found the following problem.

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

After 2 days work and studying it i had nothing. i checked the given soluton and i still can not understand the solution after debugging it step by step. 

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

The solution is quite short and its logic is combination based. What do you think about it? What is the explanation of the algorithm behind it?

Regards

Upvotes: 2

Views: 398

Answers (3)

fafl
fafl

Reputation: 7385

So let's say your question is:

  • Can you create a sum of 9 with the numbers [2, 3, 5, 8]?

This question is true if at least one of the following questions is true:

  • Can you create a sum of 9 with the numbers [3, 5, 8]?
  • Can you create a sum of 7 with the numbers [3, 5, 8]?

thus you replaced your initial question about a 4-element-list with two new questions about 3-element-lists.

When you do this three more times, you end up with 16 questions about 0-element-lists. And if for at least one of them the target is zero, then the answer to your initial question is yes.

Upvotes: 3

Jiri Tousek
Jiri Tousek

Reputation: 12440

It's just basic backtracking:

if (start >= nums.length) return (target == 0);

- Here we are past all inputs, and we succeeded exactly when the remaining target to fill is 0

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

- Here, we're attempting to fill the target using the element at position start:

  • shift start to next position
  • subtract the current element from target (this equals including the current element in chosen set)
if (groupSum(start + 1, nums, target)) return true;

- Here, we're attempting the same without using the element at position start

Reading from the last element:

  • if there's no more elements, we succeeded if target is 0
  • otherwise, we succeed if we can match the remaining elements against the target with or without using the current element

Upvotes: 4

Shadov
Shadov

Reputation: 5592

It's based on dynamic programming. Basically you break a single problem into many easier-to-solve subproblems.

Here is some explanation of this specific problem: click.

Upvotes: 0

Related Questions