java - 数组的组合总和 - 动态规划 - 需要修复

Question

我已经实现了代码来输出从输入数组的元素中获取目标总和的所有不同的唯一可能性。例如给定 arr -> [1, 2, 3, 5, 6, 7, 10] 和目标总和为 8，输出应该是 [1, 2, 5]， [1, 7], [2, 6], [3, 5]。在我下面的代码中，我在输出中得到了一个额外的 [2, 3]。同样对于 33 的目标，使用与上面相同的输入列表我得到奇怪的结果我需要一些帮助来修复此代码。

public class CombinationSum {

    public static void main(String[] args){

        List<Integer> temp = new ArrayList<Integer>();
        List<Set<Integer>> resultList = new ArrayList<Set<Integer>>();
        int[] arr={10,1,2,7,6,3,5};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));

        int target=8;
        sumCombinations(resultList, temp, target, arr, 0);
        System.out.printf("target is %s; resultList is %s%n",target,resultList);

        int target2=33;
        List<Integer> temp2 = new ArrayList<Integer>();
        List<Set<Integer>> resultList2 = new ArrayList<Set<Integer>>();
        sumCombinations(resultList2, temp2, target2, arr, 0);
        System.out.printf("target is %s; resultList is %s%n",target2,resultList2);          
    }

    public static void sumCombinations(List<Set<Integer>> resultList, List<Integer> temp, int target, int[] arr,
            int start){

       for (int i=start;i<arr.length;i++){
           if (arr[i]==target){
               temp.add(arr[i]);
               Set<Integer> scratch = new HashSet<Integer>(temp);
               if (!resultList.contains(scratch))
                   resultList.add(scratch);
           }
           else if (target>arr[i]){
               temp.add(arr[i]);
               sumCombinations(resultList, temp, target-arr[i], arr, start+1);
           }
           else  return; 
               if (temp.size()>0)
              temp.remove(temp.size()-1);
           }
       }
    }

输出:

target is 8; resultList is [[1, 2, 5], [1, 7], [2, 3], [2, 6], [3, 5]]`

target is 33; resultList is [[1, 2, 3, 7, 10], [1, 2, 5, 10], [1, 2, 6, 7, 10], 
[1, 2, 10], [1, 3, 6, 10], [1, 3, 5, 7, 10], [1, 3, 6, 7, 10], [1, 5, 7, 10], 
[1, 5, 6, 10], [1, 5, 6, 7], [1, 6, 7], [1, 6, 10], [2, 3, 6, 10], [2, 5, 7, 10],
[2, 6, 7, 10], [2, 3, 5, 10], [2, 3, 5, 6, 7, 10], [2, 3, 7], [2, 5, 6, 10], 
[2, 5, 7], [2, 5, 6, 7], [2, 6, 7], [2, 7, 10], [3, 7, 10], [3, 5, 7, 10], 
[3, 5, 6, 10], [3, 6, 7], [3, 5, 6, 7], [3, 5, 10], [3, 6, 7, 10], [3, 10], 
[5, 6, 7], [5, 6, 7, 10], [5, 6, 10], [5, 7], [6, 7], [6, 7, 10]]

Answer 1

你的递归调用

sumCombinations(resultList, temp, target - arr[i], arr, start + 1);

应该是这样的:

sumCombinations(resultList, temp, target - arr[i], arr, i + 1);

因为一旦您将数字 i 添加到 temp 中，此递归的完成方式将选择前面的 0..i-1 数字的所有组合都已经是考虑到，您只需调用 sumCombinations 来测试最后一次添加后的组合。

这导致一些数字被重新考虑并多次添加，例如 8 的错误解决方案 [2, 3] 实际上是 [2, 3 ,3]，当转换为 Set 时删除了重复的 3。