组合总数
程序员文章站
2024-03-15 08:34:29
...
题目
思路
本题是给定一个正整数和数组,要求在数组中找出所有可以使数字和为该正整数的组合,其中数组中的数字可以重复使用
如上图:
可以看出,当我们的target值小于等于0时便停止搜寻,所以回溯递归的基准条件就是当target小于等于0。相关代码如下:
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
if (candidates.size() == 0)return res;
sort(candidates.begin(), candidates.end());
dfs(candidates,0,candidates.size()-1,target);
return res;
}
void dfs(vector<int> candidates,int left,int right, int target) {
if (target == 0) {//当target为0,说明此时已经找到符合条件的数组
res.push_back(path);
return;
}
if (target < 0)return;
for (int i = left; i <=right; i++) {
path.push_back(candidates[i]);
dfs(candidates, i, right, target - candidates[i]);
path.pop_back();
}
}
};