首页 > 代码库 > Combination Sum I&&II
Combination Sum I&&II
Given a set of candidate numbers (C) 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.
- Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- 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]
需要注意的是题目给出的数据可能是乱序的，由于集合中每个元素可以用一次或多次，但是答案中不能有重复的组合，而且组合中的元素必须是非递减的顺序，因此刚开始需要对candidates进行排序，并且去重，然后对每个元素进行深搜。
深搜的每一步中都有两个选择，对第k个元素我们均可选也可不选
1 class Solution { 2 public: 3 vector<vector<int> > combinationSum(vector<int> &candidates, int target) { 4 vector<int> path; //存储解 5 allpath.clear(); 6 sort(candidates.begin(), candidates.end()); //排序 7 candidates.erase( unique(candidates.begin(), candidates.end()), candidates.end() ); //去重 8 dfs(candidates, path, 0, target); 9 return allpath;10 }11 12 void dfs(vector<int>& candidates, vector<int>& path, int k, int target) {13 if( k>=candidates.size() || target < 0 ) return ; //如果元素被搜完，或加上前个元素超出了target，那么是无效解14 if( target == 0 ) { //说明path中的元素相加等于target，这是有效解15 allpath.push_back(path);16 return ;17 }18 path.push_back(candidates[k]);19 dfs(candidates, path, k, target-candidates[k]); //加入第k个元素是解之一20 path.pop_back();21 dfs(candidates, path, k+1, target); //不要第k个元素的情况22 }23 24 private:25 vector< vector<int> > allpath; //记录所有解26 };
Combination Sum I&&II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。