题目描述
递归枚举,依次以每个点为起点枚举,每个点可以有一个或者多个,直到和大于等于target返回。
C++ 代码
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> path;
dfs(candidates, target, 0, path, res);
return res;
}
void dfs(vector<int> &a, int target, int start, vector<int> &path, vector<vector<int>> &res) {
if (target < 0) return ;
if (target == 0) {
res.push_back(path);
return;
}
for (int i = start; i < a.size(); i ++) {
path.push_back(a[i]);
dfs(a, target - a[i], i, path, res); //i表示枚举的起点。
path.pop_back();
}
}
};