【LeetCode】Day129-组合总和 II

题目

40. 组合总和 II【中等】

题解

前天的39. 组合总和集合中无重复数字，数字在每个组合中可以重复出现，这道题集合中有重复数字，每个数字在每个组合中只能出现一次，相同的是博主的回溯还是不会用-_-||

• 如何去除重复的集合？
• 顺序搜索，在搜索的过程中检测分支是否会出现重复结果
• 下图来源于liweiwei1419大神的题解
  

class Solution {
    int n;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>>res=new ArrayList<>();
        n=candidates.length;
        Arrays.sort(candidates);//排序是剪枝的前提
        List<Integer>combine=new ArrayList<>();
        dfs(candidates,target,combine,res,0);
        return res;
    }
    public void dfs(int[] candidates,int target,List<Integer>combine,List<List<Integer>>res,int begin){
        //找到满足条件的组合
        if(target==0){
            res.add(new ArrayList<>(combine));
            return;
        }
        for(int i=begin;i<n;i++){
            //剪枝:candidate[i]大了,后面肯定更大,组合不可能满足条件,退出循环
            if(target-candidates[i]<0)
                break;
            //剪枝:同一层相同数值的结点,从第2个开始,候选数更少,结果一定发生重复,因此跳过
            if(i>begin&&candidates[i]==candidates[i-1])
                continue;
            
            combine.add(candidates[i]);
            dfs(candidates,target-candidates[i],combine,res,i+1);
            combine.remove(combine.size()-1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

时间复杂度：$O(2^{n}n)$

空间复杂度：$O(n)$