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);
}
// Checks if the array can be split into two groups with equal sums
ReplyDeletepublic boolean splitArray(int[] nums) {
int index = 0;
int sum1 = 0, sum2 = 0;
// Start recursion from index 0 with both sums as 0
return helper(nums, index, sum1, sum2);
}
// Recursive helper function to try all possible splits
private boolean helper(int[] nums, int index, int sum1, int sum2) {
int length = nums.length;
// Base case: if we've considered all elements
if (index >= length)
// Return true if the two groups have equal sums
return sum1 == sum2;
// Try adding current element to sum1 OR sum2 and recurse
return helper(nums, index + 1, sum1 + nums[index], sum2) // Add to sum1
|| helper(nums, index + 1, sum1, sum2 + nums[index]); // Add to sum2
}