首页 > 代码库 > LeetCode39 Combination Sum
LeetCode39 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. （Medium）
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搜索，每个数可选可不选，然后在start > end或者candidates[start] > target后就return。
恰好candidates[start] = target满足时添加到结果中。
代码：
1 class Solution { 2 private: 3 vector<vector<int>>result; 4 void dfs(int start, int end, const vector<int>& candidates, int target, vector<int>& internal) { 5 if (start > end) { 6 return; 7 } 8 if (candidates[start] == target) { 9 internal.push_back(candidates[start]);10 result.push_back(internal);11 internal.pop_back();12 return; 13 }14 if (candidates[start] > target) {15 return;16 }17 dfs(start + 1, end, candidates, target, internal);18 internal.push_back(candidates[start]);19 dfs(start, end, candidates, target - candidates[start], internal);20 internal.pop_back();21 }22 public:23 vector<vector<int>> combinationSum(vector<int>& candidates, int target) {24 sort(candidates.begin(), candidates.end());25 int end = candidates.size() - 1;26 vector<int> internal;27 dfs(0, end, candidates, target, internal);28 return result;29 }30 };
LeetCode39 Combination Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。