如何仅使用递归解决分区问题

Question

我有一个分区问题，需要建议。我得到了一个长度为偶数的一维数组。我需要编写一个布尔方法来确定数组是否可以划分为两个大小相等的子数组，并且具有相等的和，不允许循环。

例如，数组#1{-3,5，-12,14，-9,13}将返回false，因为-35-12 14=-9 13，但是在左侧有4个元素，在另一侧有2个元素。

数组#2将返回true:{-3,14,12,5，-9,13}:-3 5 14=12-9 13

这是我到目前为止所做的：

public static boolean canBeDividedEqually(int[] arr)
{
    if (arr.length %2 ==0){
        return canBeDividedEquallyHelper(arr, 0, 0, 0);
    }
    return false;
}

public static boolean canBeDividedEquallyHelper(int[] arr, int i, int sum1, int sum2)
{
    if (i == arr.length){
        return sum1 == sum2;}
    
    return canBeDividedEquallyHelper(arr, i+1, sum1 + arr[i], sum2) ||
           canBeDividedEquallyHelper(arr, i+1, sum1, sum2 + arr[i]);
}

对于案例2，它将按预期返回true，但对于案例1，它也将返回true。我需要添加一个条件来取消case#1类型数组的资格。

Answer 1

试试这个。

static boolean canPartitioning(int[] arr) {
    return new Object() {
        int length = arr.length, half = length / 2;

        boolean partition(int i, int selected, int sum, int rest) {
            if (i >= length)
                return selected == half && sum == rest;
            return selected < half && partition(i + 1, selected + 1, sum + arr[i], rest)
                || partition(i + 1, selected, sum, rest + arr[i]);
        }
    }.partition(0, 0, 0, 0);
}


public static void main(String[] args) {
    System.out.println(canPartitioning(new int[] {-3, 5, -12, 14, -9, 13}));
    System.out.println(canPartitioning(new int[] {-3, 14, 12, 5, -9, 13}));
}

输出：

false
true

Answer 2

你就快到了。除了总和之外，还要传递元素数：

public class Solver
{
    public static boolean canBeDividedEqually(int[] arr)
    {
        return canBeDividedEquallyHelper(arr, 0, 0, 0, 0, 0);
    }

    public static boolean canBeDividedEquallyHelper(int[] arr, int i, int nb1, int sum1, int nb2, int sum2)
    {
        if (i == arr.length)
            return nb1 == nb2 && sum1 == sum2;
        return canBeDividedEquallyHelper(arr, i+1, nb1+1, sum1 + arr[i], nb2, sum2) ||
               canBeDividedEquallyHelper(arr, i+1, nb1, sum1, nb2+1, sum2 + arr[i]);
    }

    public static void main(String[] args)
    {
        System.out.println(canBeDividedEqually(new int[]{-3, 5, -12, 14, -9, 13})); // false
        System.out.println(canBeDividedEqually(new int[]{-3, 14, 12, 5, -9, 13})); // true
    }
}

Answer 3

这里有一个不使用循环的解决方案，

static int[] arrA, arrB;
    public static boolean equalSplit(int[] arr) {
        //Step 1
        if (arr.length % 2 == 0) {
            int sumA = 0, sumB = 0; // Two int variables to store the value of sum.

            // Initializing the two new arrays with equal length.
            arrA = new int[arr.length / 2]; 
            arrB = new int[arr.length / 2];

            // Copying the elements from the given array to the new arrays.
            arrA = createArray(arrA, 0, arr, 0);
            arrB = createArray(arrB, 0, arr, arr.length / 2);

            //Calculating and storing the sum in the variables.
            sumA = arraySum(arrA, arrA.length);
            sumB = arraySum(arrB, arrB.length);

            return sumA == sumB; // Checking the codition

        } else {
            return false;
        }
    }

    private static int[] createArray(int[] arr, int index, int[] copyFrom, int copyFromIndex) {
        if(index == arr.length) return arr;
        arr[index] = copyFrom[copyFromIndex];
        index++;
        copyFromIndex++;
        return createArray(arr, index, copyFrom, copyFromIndex);
    }

    private static int arraySum(int[] arr, int N) {
        if (N <= 0) return 0;
        return (arraySum(arr, N - 1) + arr[N - 1]);
    }

我对这个问题的态度是，

第一步-

步骤2-

步骤3-

步骤4-

说明：

创建两个新的整数数组，只有当给定数组可以分成两个相等的部分时，才会填充它们。这是arrA和arrB。

检查给定数组的长度是否可以被2除，并且是否有0个余数，因为这可以回答“此数组可以被分成两个相等的部分吗？”。此答案中的代码段是arr.length%2==0。如果给定数组仅满足此条件，则将执行下面给出的步骤，否则将返回false。

初始化两个整数变量以存储两个等分数组的和的值。

初始化两个新创建的数组，数组长度为给定数组的一半，即arr.length/2。

然后将给定数组元素的前半部分复制到第一个新初始化的数组中，然后将第二部分复制到第二个数组中。为了实现这个createArray（int[]arr，int index，int[]copyFrom，int copyFromIndex）方法被使用。arr是传递应复制到的数组的参数，索引应为0，因为它用作新创建数组的索引，copyFrom是包含所有元素的给定数组的参数，copyFromIndex用于开始从给定索引复制元素。

然后使用递归函数计算和，并将其存储在前面创建的单独变量中。这里使用的函数是arraySum（int[]arr，int N）。

返回两个总和变量是否相等。