Krahets 笔面试精选 88 题——40. 组合总和 II

使用深度搜索的方法：
由于题目说候选数组中的每个数字在每个组合只能出现一次，所以，为了避免重复，在开始之前对候选数组进行升序排序，这样优先选择小的数，如果当前的数都小于目标值，则后面的数就不用递归了。
具体步骤：
1、定义一个列表freq，每一个元素都是一个数组，其中第一个元素代表候选数字，第二个元素代表数字在候选数组中出现的次数。
2、定义深度优先搜索方法，pos代表当前处理位置，rest代表剩余目标数。
当目标数为0，则说明已经找到了满足条件的组合，就把暂存元素的列表sequence加入ans中，如果pos超过了freq范围，或者rest小于当前元素，则返回，说明不符合，如以上两种都不满足，就进入一个搜索循环，这里要计算most变量，代表最多可以计算几次当前数值，rest / freq.get(pos)[0]：这部分计算表示在当前剩余的目标值 rest 中，最多可以添加多少个当前数字 ，freq.get(pos)[1]：这部分计算表示当前数字在候选数组中的出现次数，将这两个数字较小的返回，这样才能添加不会超过目标值的数量。

class Solution {
    List<int[]> freq = new ArrayList<int[]>();
    //第一个元素表示候选数字，第二个元素表示该数字在候选数组中的出现次数。
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target){
        Arrays.sort(candidates);
        for(int num:candidates){
            int size = freq.size();
            if(freq.isEmpty()||num!=freq.get(size-1)[0]){
                freq.add(new int[]{num,1});
            }else{
                ++freq.get(size-1)[1];
            }
        }
        dfs(0,target);
        return ans;
    }
    public void dfs(int pos,int rest){
        //当目标数为0,说明全部找到了
        if(rest==0){
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        //如果pos超出当前freq范围，或者rest小于当前数值，则返回，不再继续
        if(pos==freq.size()||rest < freq.get(pos)[0]){
            return;
        }
        dfs(pos+1,rest);

        int most=Math.min(rest/freq.get(pos)[0],freq.get(pos)[1]);
        for(int i=1;i<=most;++i){
            sequence.add(freq.get(pos)[0]);
            dfs(pos+1,rest-i*freq.get(pos)[0]);
        }
        for(int i=1;i<=most;++i){
            sequence.remove(sequence.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
31
32
33
34
35
36
37
38
39
40