39. 组合总和#

1
给定一个无重复元素的正整数数组 candidates 和一个正整数 target
2

3
找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
4

5
candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。
6

7
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
8

9

10

11
示例 1：
12

13
输入: candidates = [2,3,6,7], target = 7
14
输出: [[7],[2,2,3]]
15
示例 2：
16

17
输入: candidates = [2,3,5], target = 8
18
输出: [[2,2,2,2],[2,3,3],[3,5]]
19
示例 3：
20

21
输入: candidates = [2], target = 1
22
输出: []
23
示例 4：
24

25
输入: candidates = [1], target = 1
26
输出: [[1]]
27
示例 5：
28

29
输入: candidates = [1], target = 2
30
输出: [[1,1]]
31

32

33
提示：
34

35
1 <= candidates.length <= 30
36
1 <= candidates[i] <= 200
37
candidate 中的每个元素都是独一无二的。
38
1 <= target <= 500

1
class Solution {
2
public:
3
    void dfs(
4
        vector<int>& candidates, int target, vector<vector<int>>& ans,
5
        vector<int>& combine, int idx
6
    ) {
7
        if (idx == candidates.size()) return;
8

9
        if (target == 0) {
10
            ans.emplace_back(combine);
11
            return;
12
        }
13

14
        dfs(candidates, target, ans, combine, idx + 1);
15

16
        if (target - candidates[idx] >= 0) {
17
            combine.emplace_back(candidates[idx]);
18
            dfs(candidates, target - candidates[idx], ans, combine, idx);
19
            combine.pop_back();
20
        }
21
    }
22

23
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
24
        vector<vector<int>> ans;
25
        vector<int> combine;
26
        dfs(candidates, target, ans, combine, 0);
27
        return ans;
28
    }
29
};