Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
target) will be positive integers.Example 1:
Input: candidates =[2,3,6,7],target =7, A solution set is: [ [7], [2,2,3] ]
Example 2:
Input: candidates = [2,3,5],target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ]
考察要点: 基本的DFS, 其他没有难度, 注意数组的元素可以被重复利用
class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); vector<vector<int>> res; vector<int> candi; traverse(candidates,target,res,candi,0); return res; } void traverse(vector<int> &candidates,int target, vector<vector<int>> &res, vector<int> &cur, int index) { if(0==target) { res.push_back(cur); return; } for(;index<candidates.size()&&target>=candidates[index];++index) { cur.push_back(candidates[index]); traverse(candidates,target-candidates[index],res,cur,index); cur.pop_back(); } } };
原文：https://www.cnblogs.com/lychnis/p/11704868.html