Java > Recursion-2 > splitArray (CodingBat Solution)

Problem:

Given an array of ints, is it possible to divide the ints into two groups, so that the sums of the two groups are the same. Every int must be in one group or the other. Write a recursive helper method that takes whatever arguments you like, and make the initial call to your recursive helper from splitArray(). (No loops needed.)

splitArray({2, 2}) → true
splitArray({2, 3}) → false
splitArray({5, 2, 3}) → true


Solution:

public boolean splitArray(int[] nums) {
  int index = 0;
  int sum1 = 0;
  int sum2 = 0;
  return recArray(nums, index, sum1, sum2);
}

private boolean recArray ( int[] nums, int index, int sum1, int sum2 ) {
  if ( index >= nums.length ) {
    return sum1 == sum2;
  }

  int value = nums[index];

  return (recArray(nums, index + 1, sum1 + value, sum2) || 
    recArray(nums, index + 1, sum1, sum2 + value));
}


5 comments :

  1. public boolean splitArray(int[] nums) {
      return groupSum(0,nums,0,0);
    }
    private boolean groupSum(int start,int[] nums,int sum1,int sum2) {
      if (start >= nums.length) return sum1==sum2;
      if (groupSum(start+1,nums,sum1+nums[start],sum2)) return true;
      if (groupSum(start+1,nums,sum1,sum2+nums[start])) return true;
      return false;
    }

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

    ReplyDelete
  3. public boolean splitArray(int[] nums) {

    return helper(0,nums,0,0);
    }

    public boolean helper(int start, int[] nums, int left, int right){
    if(start == nums.length){
    return left == right;
    }
    if(helper(start + 1, nums, left + nums[start], right))
    return true;
    if(helper(start + 1, nums, left, right + nums[start]))
    return true;

    return false;

    }

    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