I'm trying to write a method that would Return true if it is possible to divide all the members of an array into two different groups of equal size so that the sum of the members of the two groups is equal. If this is not possible, the method Return false.
public static boolean equalSplit (int[] arr){
if(arr.length % 2 != 0) // if array length is not equal both sides
return false;
return equalSplit (arr, arr[0],(0 + arr.length-1) / 2 , arr.length-1);
}
public static boolean equalSplit (int[] arr, int start, int mid, int end){
}
I got stuck here and i have no clue what to do next.
I made this code but it doesn't check all possibilities , but I think its a good start :
public static boolean equalSplit (int[] arr){
if(arr.length % 2 != 0) // if array length is not equal both sides
return false;
return equalSplit (arr, 0 ,(0 + arr.length-1) / 2 , arr.length-1 , 0 , 0);
}
public static boolean equalSplit (int[] arr, int start, int mid, int end,int sumStart,int sumEnd){
if(start == mid){// both sides have the same iterations
return sumEnd == sumStart ;
}
sumStart += arr[start];
sumEnd += arr[end];
start ++;
end--;
return equalSplit ( arr, start, mid, end ,sumStart , sumEnd) ;
}
something like this should solve your problem and handle all cases.
public static boolean canBeDividedEqually(int[] arr) {
if (arr.length % 2 != 0) {
return false;
}
int sum = getSum(arr);
if (sum % 2 != 0) {
return false;
}
return canBeDividedEqually(arr, sum);
}
public static int getSum(int[] arr) {
return getSum(arr, 0, 0);
}
private static int getSum(int[] arr, int sum, int index) {
if (index >= arr.length) {
return sum;
}
return getSum(arr, sum + arr[index], index + 1);
}
private static boolean canBeDividedEqually(int[] arr, int sum) {
// this can be optimized by canBeDividedEqually(arr, sum/2, arr[0], arr.length/2, 1, 1) because first element should always belong to first group, so we can start search from second element
return canBeDividedEqually(arr, sum/2, 0, arr.length/2, 0, 0);
// return canBeDividedEqually(arr, sum/2, arr[0], arr.length/2, 1, 1);
}
private static boolean canBeDividedEqually (int[] arr, int searchSum, int currentSum, int searchQuantity, int currentQuantity, int nextIndex) {
if(searchSum == currentSum && searchQuantity == currentQuantity) {
return true;
}
if(searchSum <= currentSum || searchQuantity <= currentQuantity) {
// we have too big sum or we take to much elements
return false;
}
if(nextIndex + (searchQuantity - currentQuantity) > arr.length) {
// we need to take more elements than we have still available
return false;
}
// add current element into account and search further
if(canBeDividedEqually(arr, searchSum, currentSum + arr[nextIndex], searchQuantity, currentQuantity + 1, nextIndex + 1)) {
System.out.println("true");
return true;
}
// if above "if" statement is not true, then skip current element and try to search further
return canBeDividedEqually(arr, searchSum, currentSum, searchQuantity, currentQuantity, nextIndex + 1);
}