题目简介:
给定一个无重复元素的数组 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的数字可以无限制重复被选取。
说明:
- 所有数字(包括
target
)都是正整数。
- 解集不能包含重复的组合。
示例 1:
1 2 3 4 5 6
| 输入:candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ]
|
示例 2:
1 2 3 4 5 6 7
| 输入:candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]
|
提示:
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate
中的每个元素都是独一无二的。
1 <= target <= 500
思路:
又是一道回溯题,和昨天的题一样,需要注意的是每次都要从上个数字的位置开始往后遍历,这样才能避免重复。
还有一点比较重要的是当target < 0
时,无论后面怎么取都不可能使target == 0
了(元素都为正数),所以直接return
即可。
代码如下:
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
| class Solution { public:
vector<vector<int>> res;
void dfs(vector<int>& candidates, int target, vector<int>& temp, int pos){
if(target == 0){
res.push_back(temp); return; }
if(target < 0) return;
for(int i = pos; i < candidates.size(); i++){
temp.push_back(candidates[i]);
dfs(candidates, target - candidates[i], temp, i);
temp.pop_back(); } }
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> temp;
dfs(candidates, target, temp, 0);
return res;
} };
|