非死不可面筋

楼主好运，东方不亮西方亮。

觉得楼主的time complexity 没有错 dfs index recurison 维持同一个index 然后 每一次选择要去重 dp 这个能做吗? 用backtracking 感觉能做 但是颇麻烦...

如果真是国人面试官，可能还有一点过得希望吧


就是dfs啊，然后每次recursive的时候指针不+1

复杂度我也赞成m^n
不过这个m^n是有点粗犷的，可以更加准确

say543 发表于 2017-5-23 15:04
觉得楼主的time complexity 没有错 dfs index recurison 维持同一个index 然后 每一次选择要去重 dp 这个能 ...

去重其实你在做dfs之前先给数组去重自然在做dfs的时候就不用考虑了

lz这个就是combination sum 1 + 2 啊

我写了下

1.     void perm(vector<int>& nums, int pos, int target, vector<int>& temp, vector<vector<int>>& rslt) {
   
2.         if (target == 0) {
   
3.             rslt.push_back(temp);
   
4.         } else if (target < 0) {
   
5.             return;
   
6.         }
   
7.         
   
8.         for (int i = pos; i < nums.size();) {
   
9.             temp.push_back(nums[i]);
   
10.             perm(nums, i, target - nums[i], temp, rslt);
    
11.             temp.pop_back();
    
12.             
    
13.             int p = i;
    
14.             while ((nums[p] == nums[i]) && (p < nums.size())) p++;
    
15.             i = p;
    
16.         }
    
17.     }

复制代码

输入{1, 1, 1, 1, 2, 3}, target = 5的结果是

1. 1, 1, 1, 1, 1,
   
2. 1, 1, 1, 2,
   
3. 1, 1, 3,
   
4. 1, 2, 2,
   
5. 2, 3,

复制代码

sfsttz 发表于 2017-5-23 08:43
他问“target大小是m，数组长度是n” 可能说明他想要dp做法

求所有解，不能DP，要深搜

嘛，总体来说不难，就是一时脑残：

1. public List<List<Integer>> combinationSum2(int[] candidates, int target) {
   
2.                 List<List<Integer>> res = new ArrayList<>();
   
3.                 if (candidates == null || candidates.length == 0) {
   
4.                         return res;
   
5.                 }
   
6. 
   
7.                 ArrayList<Integer> tmp = new ArrayList<>();
   
8.                 dfsHelper(tmp, res, target, 0, candidates);
   
9. 
   
10.                 return res;
    
11.         }
    
12. 
    
13.         private void dfsHelper(ArrayList<Integer> tmp, List<List<Integer>> res, int target, int start, int[] candidates) {
    
14.                 if (target == 0) {
    
15.                         res.add(new ArrayList<>(tmp));
    
16.                         return;
    
17.                 }
    
18. 
    
19.                 for (int i = start; i < candidates.length; i++) {
    
20.                         if (i != start && candidates[i] == candidates[i - 1]) {
    
21.                                 continue;
    
22.                         }
    
23. 
    
24.                         if (candidates[i] > target) {
    
25.                                 break;
    
26.                         }
    
27. 
    
28.                         tmp.add(candidates[i]);
    
29.                         dfsHelper(tmp, res, target - candidates[i], i, candidates);
    
30.                         tmp.remove(tmp.size() - 1);
    
31.                 }
    
32.         }

复制代码

lc上有一篇关于此类题目的总结很好，都是backtracking
https://discuss.leetcode.com/topic/46159/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partitioning

谢谢分享
楼主好运啊！！

bless LZ. 这个跟LC的combination（可以重复取值那道）有啥区别啊？感觉是一样啊