Java > Recursion-2 > groupSum (CodingBat Solution)

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


Solution:

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

  return false;
}


3 comments :

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

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

    ReplyDelete
  3. this code will fail for following test case...groupSum(0,[2,4,8], 0)..it returns true..but the answer should be false..how to fix this?

    ReplyDelete

Follow Me

If you like our content, feel free to follow me to stay updated.

Subscribe

Enter your email address:

We hate spam as much as you do.

Upload Material

Got an exam, project, tutorial video, exercise, solutions, unsolved problem, question, solution manual? We are open to any coding material. Why not upload?

Upload

Copyright © 2012 - 2014 Java Problems  --  About  --  Attribution  --  Privacy Policy  --  Terms of Use  --  Contact