题目

给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。

示例1：

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
1
2
3
4
5
6
7
8

示例2：

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
1
2
3
4
5
6

提示

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

思路1

链接

class Solution {
public:
    /*
        1-candidates中的数字在一个组合中只能使用一次。因此，我们在递归到下一层的时候要从当前层起点的下一个开始循环；
        2-数组可能有重复元素，因此一开始我们要对数组进行排序。然后，在同一层的循环中，对于起点之后的数，要盘与之前的数是否一样，如果一样，则不进行处理，一次避免出现重复的组合。
    */
    vector<vector<int>>res;
    void dfs(vector<int>&candidates, int target, int ind, vector<int> tmp){
        if(target<0){
            return;
        }
        if(target==0){
            res.emplace_back(tmp);
            return;
        }

        //经过排序，若减法后有小于0的，则后面的也可以不用考虑，此处是>=0，而不是>0，>0会导致结果空集
        //1-i往下走，避免组合内的重复
        for(int i = ind ; i<candidates.size() && target-candidates[i]>=0; i++){
            //2-i>ind非常关键，即从起点之后才考虑重复，避免组合内的重复
            //1 +2 联合起来，取出组合内的重复
            if(i> ind && candidates[i] == candidates[i-1]){
                continue;
            }
            tmp.emplace_back(candidates[i]);
            dfs(candidates, target-candidates[i], i+1, tmp);  //从下一个元素开始，避免元素的重复选取
            tmp.pop_back();
        }

    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int>tmp;
        dfs(candidates, target, 0, tmp);
        return res;
    }
};
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

思路2-回溯法+递归法

• dfs(pos,rest)表示递归的函数，其中pos表示我们当前递归到了数组candidates中的第pos个数，而rest表示我们还需要选择和为rest的数放入列表作为一个组合；
• 对于当前的第pos个数，我们有两种方法：选或者不选。如果我们选择了这个树，那么我们调用dfs(pos+1,rest-candidates[pos])进行递归，注意这里必须满足rest>=candidates[pos]。如果我们不选这个数，那么我们调用dfs(pos+1,rest)进行递归；
• 在某次递归开始前，如果rest的值未0，说明我们找到了一个和为target的组合，将其放入答案中。每次调用递归函数前，如果我们选了那个数，就需要将其放入列表的末尾，该列表中存储了我们所选的所有数。在回溯时，如果我们选了那个数，就要将其从列表的末尾删除。

上述算法就是一个标准的递归 + 回溯算法，但是它并不适用于本题。这是因为题目描述中规定了解集不能包含重复的组合，而上述的算法中并没有去除重复的组合。

例如当 \textit{candidates} = [2, 2]candidates=[2,2]，\textit{target} = 2target=2 时，上述算法会将列表 [2][2] 放入答案两次。
1

因此，我们需要改进上述算法，在求出组合的过程中就进行去重的操作。我们可以考虑将相同的数放在一起进行处理，也就是说，如果数 x 出现了 y 次，那么在递归时一次性地处理它们，即分别调用选择 0, 1, ⋯,y 次 x 的递归函数。这样我们就不会得到重复的组合。具体地：

• 我们使用一个哈希映射（HashMap）统计数组candidates 中每个数出现的次数。在统计完成之后，我们将结果放入一个列表 freq 中，方便后续的递归使用。

列表 freq 的长度即为数组 candidates 中不同数的个数。其中的每一项对应着哈希映射中的一个键值对，即某个数以及它出现的次数。

• 在递归时，对于当前的第 pos 个数，它的值为 freq[pos][0]，出现的次数为freq[pos][1]，那么我们可以调用

dfs(pos+1,rest−i×freq[pos][0])

即我们选择了这个数 ii 次。这里 ii 不能大于这个数出现的次数，并且 i×freq[pos][0] 也不能大于rest。同时，我们需要将 i 个freq[pos][0] 放入列表中。

这样一来，我们就可以不重复地枚举所有的组合了。

我们还可以进行什么优化（剪枝）呢？一种比较常用的优化方法是，我们将 freq 根据数从小到大排序，这样我们在递归时会先选择小的数，再选择大的数。这样做的好处是，当我们递归到textit{pos}, dfs(pos,rest) 时，如果freq[pos][0] 已经大于rest，那么后面还没有递归到的数也都大于 rest，这就说明不可能再选择若干个和为 rest 的数放入列表了。此时，我们就可以直接回溯。

class Solution {
private:
    vector<pair<int, int>> freq;
    vector<vector<int>> ans;
    vector<int> sequence;

public:
    void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.push_back(sequence);
            return;
        }
        if (pos == freq.size() || rest < freq[pos].first) {
            return;
        }

        dfs(pos + 1, rest);

        int most = min(rest / freq[pos].first, freq[pos].second);
        for (int i = 1; i <= most; ++i) {
            sequence.push_back(freq[pos].first);
            dfs(pos + 1, rest - i * freq[pos].first);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.pop_back();
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        for (int num: candidates) {
            if (freq.empty() || num != freq.back().first) {
                freq.emplace_back(num, 1);
            } else {
                ++freq.back().second;
            }
        }
        dfs(0, target);
        return ans;
    }
};
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
41