Combination sum 迭代

其实这个思路应该叫backtracking

1.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
   
2.         List<List<Integer>> result = new ArrayList<List<Integer>>();
   
3.         Arrays.sort(candidates); // sort the array
   
4.         recurse(new ArrayList<Integer>(), target, candidates, 0, result);
   
5.         return result;
   
6.     }
   
7. 
   
8.     /**
   
9.      * do it recursively
   
10.      */
    
11.     private void recurse(List<Integer> list, int target, int[] candidates, int index, List<List<Integer>> result) { // list is one of the answers
    
12.         if (target == 0) {
    
13.             result.add(list);
    
14.             return;
    
15.         }
    
16.         for (int i = index; i < candidates.length; i++) {
    
17.             int newTarget = target - candidates[i]; // subtract candidate from target
    
18.             if (newTarget >= 0) {
    
19.                 List<Integer> copy = new ArrayList<Integer>(list); // create a copy
    
20.                 copy.add(candidates[i]);
    
21.                 recurse(copy, newTarget, candidates, i, result); // see if there is more
    
22.             } else { // run out of target
    
23.                 break;
    
24.             }
    
25.         }
    
26.     }

复制代码

Adeath 发表于 2014-11-3 12:39
我觉得DP不适合这道题，DP比较少用来发现全部答案的集合，通常是发现数量。一个集合的combination，每个元 ...

你说的很对，DP在这里并不适用。

combination sum或者subset sum要想象所有的解空间是一颗树，每个节点的值是当前子集加起来的和，要遍历这个解空间得到答案。比如说{1, 2, 3}，3
                         0
             1                      0                     (with 1 or without 1)
        3        1            2        0                (with 2 or without 2)
    6    3    4    1    5    2    3    0             (with 3 or without 3)

backtracking已经是最好的思想了，一旦不符合条件就尝试其他分支。树的节点有2^n个，最坏情况遍历整棵树，逃不开2^n的。

最近也刷这道题，小挖个坟，提供一个从同学那儿学到的DP的思路。DP应该是有两种情况吧，一个是以当前状态更新之后状态，我提供的思路就是这个；另一个是当前状态用之前的状态计算，类似LCS就是这类。虽然听起来似乎一样但是操作起来不一样。
拿个例子说一下，比如给[2,3,7] target = 7.
首先DP需要一个三维数组DP[][][]保存结果，初始化其长度为1+target，因为其中DP[0]的结果需要初始化为[]。然后就从DP[0]开始增长。
DP[0]: []
从左扫到右，0+2和0+3是小于target的，0+7刚好是target，于是更新为：
DP[0]: []
DP[2]: [2]
DP[3]: [3]
DP[7]: [7]
接下来找DP[1]发现没有解，跳过，找DP[2]，更新为：
DP[0]: []
DP[2]: [2]
DP[3]: [3]
DP[4]: [2,2]
DP[5]: [2,3]
DP[7]: [7]
以此类推，最后用DP[target-1]更新完之后，DP[target]就是想要的结果。
不过假设candidates的长度是n，DP中最长的解集个数是m，那么时间复杂度和空间复杂度都是O(n*m*target)了。

表示也刚刷到这道题，用recursion挺方便的啊，包括八皇后，subset，permutations都用recursion的套路我觉得很好用。

这个随便一搜都有吧，思路就是用recursion，只有sum等于target的时候才要返回结果。

我觉得DP不适合这道题，DP比较少用来发现全部答案的集合，通常是发现数量。一个集合的combination，每个元素都有可能出现或者不出现，也就是说worst case复杂度就是2^n， 不可能做到n^2的。