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

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.