java - 找出数组中和相同的两个子集

Question

我尝试解决一个编码问题，该问题要求我给出具有相同总和的数组中的两个子集。

例如，我们的输入可以是[3,1,2,4]。我对此问题的预期解决方案是 [[3,2],[1,4]] 或 [[2,3],[4,1]](可以接受。但不接受重复的答案，例如 [[3,2],[1,4],[2,3],[4,1]])，因为 1 + 4 = 2 + 3。如果我的输入不能产生这样的组合，我的代码可以只输出 Null 或 [[]]。

我尝试使用DFS(深度优先搜索)来解决这个问题，我当前的代码如下所示:

public static List<List<Integer>> twoPartSum(int[] arr){

    // corner case

    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> part = new ArrayList<>();

    if(arr == null || arr.length <= 1){
        ret.add(part);
        return ret;
    }

    // usual case

    int sum = 0;
    for(int i : arr){
        sum += i;
    }

    helper(arr, 0, sum/2, 0, ret, part);

    return ret;

}

private static void helper(int[] arr, int curSum ,int target, int index, List<List<Integer>> ret, List<Integer> part){

    //base case
    if(curSum == target){

        ret.add(new ArrayList<>(part));
        return;
    }

    // such a pair does not exits
    if(curSum > target ){
        return;
    }


    for(int i = index; i < arr.length; i++){

        swap(arr, i, index);
        curSum += arr[index];
        part.add(arr[index]);

        helper(arr, curSum, target, index + 1, ret, part);

        curSum -= arr[index];
        part.remove(index);
        swap(arr, i, index);

    }


}

private static void swap(int[] arr, int i, int j){

    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;

}

我当前的结果是 [[3,2],[1,4],[2,3],[4,1]]，输入为 [3,1, 2,4] 不幸的是，我不知道如何对结果进行重复数据删除。有人可以提供一些想法吗？提前致谢!

输入中可能存在重复的数字，例如[3,1,1,1,2,4]。而且，显然我当前的解决方案无法涵盖这种情况。如果您也能提供这样的通用算法，我将不胜感激。但如果它太困难，我会很高兴现在知道不同数组的解决方案。

Answer 1

为了对结果进行重复数据删除，您可以对子集进行排序，即每个子集中的元素必须按升序排列(如果您愿意，也可以按降序排列)。这意味着 [3,2] 将被重写为 [2,3]，因此您将检索 [2,3],[2, 3],[1,4],[1,4] 在您的示例中。如果您将子集存储在 Set 中而不是 ArrayList 中，则首先不会添加重复项，并且您将得到 [2,3] ，[1,4]。