首页 > 代码库 > [leetcode-39-Combination Sum]
[leetcode-39-Combination Sum]
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]
]
思路:
典型回溯法。
void combinationSum(vector<vector<int>>&ret, vector<int>& temp, vector<int>& candidates, int target,int begin) { if (target==0) { ret.push_back(temp); return; } for (int i = begin; i < candidates.size() && candidates[i]<=target;i++) { temp.push_back(candidates[i]); combinationSum(ret, temp, candidates, target - candidates[i],i); temp.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>>ret; vector<int>temp; sort(candidates.begin(), candidates.end()); combinationSum(ret, temp, candidates, target,0); return ret; }
参考:
https://discuss.leetcode.com/topic/14654/accepted-16ms-c-solution-use-backtracking-easy-understand
[leetcode-39-Combination Sum]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。