Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is: [ [7], [2, 2, 3] ]
方法:DFS
class Solution { private: void find(vector<vector<int>>& res,vector<int>& candidates,vector<int>& buffer, const int& target, int index,int temp_sum){ if(temp_sum > target){ return; } else if(temp_sum == target){ res.push_back(buffer); return ; } for(int i = index ; i < candidates.size() ; ++i){ buffer.push_back(candidates[i]); find(res,candidates,buffer,target,i,temp_sum+candidates[i]); buffer.pop_back(); } } public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> res; vector<int> buffer; find(res,candidates,buffer,target,0,0); return res; } };