03.03回溯法

 

class Solution {
public:vector<int> temp;vector<vector<int>> ans;void dfs(int cur,int n,int k){//剪枝 temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 tempif(temp.size()+(n-cur+1)<k){return;}if(temp.size()==k){ans.push_back(temp);return;}temp.push_back(cur);dfs(cur+1,n,k);temp.pop_back();dfs(cur+1,n,k);}vector<vector<int>> combine(int n, int k) {dfs(1,n,k);   return ans;}
};

class Solution {
public:void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combination, int idx){if(candidates.size()==idx){return;}if(target==0){ans.push_back(combination);return;}//直接跳过dfs(candidates,target,ans,combination,idx+1);//选择当前数if(target-candidates[idx]>=0){combination.emplace_back(candidates[idx]);//继续添加当前元素dfs(candidates,target-candidates[idx],ans,combination,idx);combination.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector< vector<int> >ans;vector<int> combination;dfs(candidates,target,ans,combination,0);return ans;}
};