获取整数数组的布尔递归静态方法

Question

我正在尝试编写一个方法，如果可以将数组的所有成员划分为两个大小相等的不同组，使这两个组的成员之和相等，则该方法将返回true。如果这不可能，则方法Return为false。

条件是：

• 这个方法应该是递归的，根本不使用循环，所有的辅助方法也是不能包含循环
  
• 数组既不为null也不为空
• 不要修改数组的内容(即使是临时的(，也不要使用辅助数组

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){

}

我被困在这里，不知道下一步该怎么办。

Answer 1

我编写了这段代码，但它没有检查所有的可能性，但我认为这是一个好的开始：

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) ;
}

Answer 2

这样的东西应该可以解决您的问题并处理所有情况。

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);
}