Problem:
Given an array of ints, is it possible to divide the ints into two groups, so that the sum of the two groups is the same, with these constraints: all the values that are multiple of 5 must be in one group, and all the values that are a multiple of 3 (and not a multiple of 5) must be in the other. (No loops needed.)
split53({1,1}) → true
split53({1, 1, 1}) → false
split53({2, 4, 2}) → true
Solution:
public boolean split53(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];
if (value%5 == 0)
return recArray(nums, index + 1, sum1 + value, sum2);
else if (value%3 == 0)
return recArray(nums, index + 1, sum1, sum2 + value);
else
return (recArray(nums, index + 1, sum1 + value, sum2) ||
recArray(nums, index + 1, sum1, sum2 + value));
}
public boolean split53(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 (nums[start]%5!=0 &
groupSum(start+1,nums,sum1+nums[start],sum2))
return true;
if (nums[start]%3!=0 &
groupSum(start+1,nums,sum1,sum2+nums[start]))
return true;
return false;
}
public boolean split53(int[] nums) {
ReplyDeletefinal int index = 0;
final int sum1 = 0;
final 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);
}
if (nums[index] % 5 == 0) {
return recArray(nums, index + 1, sum1 + nums[index], sum2);
}
if (nums[index] % 3 == 0) {
return recArray(nums, index + 1, sum1, nums[index] + sum2);
}
return recArray(nums, index + 1, sum1 + nums[index], sum2)
|| recArray(nums, index + 1, sum1, nums[index] + sum2);
}