在数组中找到具有相同总和的两个子集

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].

Answer 2

我终于想出了一个更好的方法来解决这个问题。我想与对这个问题感兴趣的人分享。该代码还可以处理输入数组中的重复元素。

我改变了这个问题的逻辑。此代码的递归树如下所示。基本上，它是一棵二叉树，每个分支代表是否向数组中添加元素。数组的索引是这棵树的深度。

                       /            \
  arr[0] = 3          3(add 3)       0(don't add 3)     depth(index of the arr) == 0  
                   /      \       /      \
  arr[1] = 1    1+3      0+3     1+0      0+0           depth == 1
               /  \     /   \   /   \    /   \
  arr[2] = 2 2+4  0+4  2+3 0+3 2+1  0+1 2+0  0+0        depth == 2
             /\   /\   /\  /\   /\   /\  /\   /\ 
            ......

上面的树是对数组所有子集求和的完整解。当然，我们可以通过为这个特定问题指定停止标准来停止任何分支，即

// base case 1: found the answer
if(curSum == target){
    ret.add(new ArrayList<>(part));
    return;
}

我的问题的有效代码如下：

public static List<List<Integer>> twoPartSum2(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

    Arrays.sort(arr); // make sure the same numbers will be lined together

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

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

    return ret;

}

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

    // base case 1: found the answer
    if(curSum == target){
        ret.add(new ArrayList<>(part));
        return;
    }

    // base case 2: solution not found
    if(index == arr.length || curSum > target){
        return;
    }

    // recursion case 1: adding current element in the candidate list ("part")
    part.add(arr[index]);
    helper2(arr, curSum + arr[index], target,index + 1,ret, part);
    part.remove(part.size()-1);

    // deduplicate the same elements
    while(index + 1 < arr.length && arr[index] == arr[index+1]){
        index++;
    }

    // recursion case 2: not adding current element in the candidate list ("part")
    helper2(arr, curSum, target, index + 1,ret,part);

}

请注意，为了对我们的解决方案进行重复数据删除，我们必须跳过数组中的相同元素，这正是数组在最开始排序的原因 Arrays.sort(arr); 然后我们有以下内容在每一层跳过相同的元素。

// deduplicate the same elements
while(index + 1 < arr.length && arr[index] == arr[index+1]){
    index++;
}

例如，如果我们的数组是[1,1,1,3]。那么我们将得到一个递归树，如下所示：

                           /             \
  arr[0] = 1              1               0
                     /        \           |    (the other two '1's are skipped)
  arr[1] = 1       1+1        0+1         |     
                  /   \        |          |     (the other one '1' is skipped)   
  arr[2] = 1    1+2   0+2      |          | 
               / \    / \     / \        / \
  arr[3] = 3 3+3 0+3 3+2 0+2 3+1 0+1   3+0 0+0

答案是：6,3,5,2,4,1,3,0

有些人可能会问为什么我们有两个 3？好吧，实际上，它们在这个问题中是不同的 3 因为第一个 3 是通过 1+1+1 获得的，而第二个是来自 3，即数组中的最后一个元素 [1,1,1,3].结果，他们对这个问题还是有不同的解决方案。

我之前在这个问题中使用的逻辑仍然有效，但我现在不想 post 它，因为它更令人困惑。但是，如果有人仍然对此问题感兴趣，请发表评论，我会在有空时更新。谢谢！

在数组中找到具有相同总和的两个子集

Find the two subsets with the same sum in an array

java

knapsack-problem

depth-first-search