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

Question

我正在尝试编写一个方法，如果可以将数组的所有成员分成两组大小相等的不同组，并使得这两个组的成员总和相等，则返回true。如果不可能，该方法返回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){
       
}

我被卡在这里了，不知道下一步该怎么做。

- Ofek .D

---

那个条件与其所附带的注释无关。你认为它确切地是做什么？ - Stultuske

只使用0/1背包的概念，我认为它可以帮助检查数组是否可以分成两个具有相等和的部分。 - Rohith V

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

- Yasser CHENIK

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

- Grzegorz