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

Question

我已经实现了代码来输出从输入数组的元素中获得目标和的所有不同的唯一可能性。例如，给定arr-

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添加到拾取前一个0的所有组合中时，就会执行此递归。。已经考虑了i-1编号，您只需在最后一次添加后调用sumCombinations即可测试组合。

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