java - 最小和差的等分法

Question

我正尝试按照以下步骤用 Java 编写此算法:(我知道其他解决方案，只是想弄清楚这个)

int min_diff = LARGE_NUMBER;
int diff;
for (each subset S of size n/2 of A) {
    diff = abs(sum(S) – sum(A-S));
    if (diff < min_diff) {
        min_diff = diff;
        TempSet = S;
     }

 }
print min_diff, TempSet;

我尝试使用此链接中的代码查找大小为 n/2 的所有子集排列:https://www.geeksforgeeks.org/print-subsets-given-size-set/此链接中的代码打印所有排列。我首先想到我需要将数组存储在 ArrayList 中，以便我可以在 for 循环中使用它们，但我无法让它工作。下面的代码给出了错误的输出(每个数组都是 60 60 60 而不是排列:

static List<int[]> intArrays = new ArrayList<>();

static void combinationUtil(int[]arr, int n, int r, int index, int[] data, int i)
{

    if (index == r) {           
        intArrays.add(data);
        return;           
    }

    if (i >= n)
        return;

    data[index] = arr[i];
    combinationUtil(arr, n, r, index + 1, data, i + 1);
    combinationUtil(arr, n, r, index, data, i + 1);


}

static void printCombination(int arr[], int n, int r)
{

    int data[] = new int[r];
    combinationUtil(arr, n, r, 0, data, 0);
    for(int[] arr1:intArrays){
      System.out.println(Arrays.toString(arr1));
    }
}

public static void main(String[] args)
{
    int arr[] = { 10, 20, 30, 40,50,60};
    int n=arr.length;
    int r=n/2;

    printCombination(arr, n, r);
}

谁能告诉我我的代码有什么问题？或者我如何按照上述步骤解决这个问题？

Answer 1

您的问题是当您执行 intArrays.add(data);

intArrays 始终包含对 data 数组的引用。该数组通过引用传递。您得到 {60, 60, 60} 因为它是 data 数组(最后一个子集)的最后状态。

要解决此问题，您必须执行 intArrays.add(data.Clone()); 如果存在 Clone 函数或您的语言中的类似函数，或者自己实现.

C# 代码。抱歉，我没有安装任何 Java 编译器。

static int[] CloneArray(int[] arr)
{
    int[] ret = new int[arr.Length];
    for (int i = 0; i < arr.Length; ++i) ret[i] = arr[i];
    return ret;
}