再谈暴搜回溯问题Leetcode3940组合总和，合总和Ⅱ

每个数只能用一次，并且有重复的数，这个搜索结构和子集的搜索结构是一样的。

 

class Solution { public: vector<vector<int>> res; vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); vector<int> path; backTracking(candidates,0,target,path); return res; } void backTracking(vector<int>& candidates, int start, int target, vector<int> &path){ if(target<0) return; else if(target==0) res.push_back(path); for(int i=start;i<candidates.size();i++){ path.push_back(candidates[i]); backTracking(candidates,i+1,target-candidates[i],path); path.pop_back(); } } };

 

每个数可以无限被选择，有两种方法，一个种是对于每一个数字，枚举这个数字选多少次。

另一种是再前面的基础上，选完了还可以再选，不用往后走。

class Solution { public: vector<vector<int>> res; vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<int> path; sort(candidates.begin(),candidates.end()); backTracking(candidates,target,0,path); return res; } void backTracking(vector<int>& candidates, int target, int start, vector<int> &path){ if(target<0) return; if(target==0){ res.push_back(path); return; } for(int i=start;i<candidates.size();i++){ path.push_back(candidates[i]); backTracking(candidates,target-candidates[i],i,path); path.pop_back(); } } };