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));
}
;kj
ReplyDelete;kj
ReplyDeletepublic boolean splitArray(int[] nums) {
ReplyDeletereturn 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;
}
public boolean splitArray(int[] nums) {
ReplyDeletereturn 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]);
}
public boolean splitArray(int[] nums) {
ReplyDeletereturn 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;
}
public boolean splitArray(int[] nums) {
ReplyDeletereturn groupSum(0, nums, 0, 0);
}
private boolean groupSum(int start,int[] nums,int sum1,int sum2) {
if (start >= nums.length){
return (sum1 == sum2);
}
return groupSum(start + 1, nums, sum1 + nums[start], sum2)
|| groupSum(start + 1, nums, sum1, nums[start] + sum2);
}