首页 > 代码库 > 【Lintcode】135.Combination Sum
【Lintcode】135.Combination Sum
题目:
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.
Example
Given candidate set [2,3,6,7]
and target 7
, a solution set is:
[7]
[2, 2, 3]
题解:
这个题和LeetCode不一样,这个允许重复数字产生,那么输入[2,2,3],7 结果为[2, 2, 3], [2, 2, 3], [2, 2, 3];要么对最后结果去除重复数组,要么在处理之前就对candidates数组去重复,或者利用set不重复的特点添加数组。
Solution 1 ()
class Solution { public: vector<vector<int> > combinationSum(vector<int> &candidates, int target) { if (candidates.empty()) { return {{}}; } set<vector<int> > res; vector<int> cur; sort(candidates.begin(), candidates.end()); dfs(res, cur, candidates, target, 0); return vector<vector<int> > (res.begin(), res.end()); } void dfs(set<vector<int> > &res, vector<int> &cur, vector<int> candidates, int target, int pos) { if (!cur.empty() && target == 0) { res.insert(cur); return; } for (int i = pos; i < candidates.size(); ++i) { if (target - candidates[i] >= 0) { cur.push_back(candidates[i]); dfs(res, cur, candidates, target - candidates[i], i); cur.pop_back(); } else { break; } } } };
【Lintcode】135.Combination Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。