:::tip
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
思路分析:对于每一次递归都有两种情况,一种是选取这一位,一种是不选取这一位;
:::
class Solution {
public:
vector<int> path; // 存储路径
vector<vector<int>> ans; // 存储答案
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates, 0, target);
return ans;
}
void dfs(vector<int> &candidates, int u, int target)
{
// 达到目标停止递归
if(target == 0)
{
ans.push_back(path);
return;
}
// 和的输入超过target了,停止递归
if(target < 0) return;
if(u == candidates.size()) return;
// 不选取自己
dfs(candidates,u+1,target);
// 选取自己
path.push_back(candidates[u]);
dfs(candidates,u,target-candidates[u]);
path.pop_back();
}
};