LintCode: Combination Sum II

简介:

C++

DFS

复制代码
 1 class Solution {
 2 public:
 3     void help(vector<int> &a, int now, int sum, int target, vector<int> &path, vector<vector<int> > &ans, bool last) {
 4         if (sum > target) {
 5             return ;
 6         }
 7         if (now >= a.size()) {
 8             if (sum == target) {
 9                 ans.push_back(path);
10             }
11             return ;
12         }
13         if ((now == 0) || (a[now - 1] != a[now]) || last) {
14             path.push_back(a[now]);
15             help(a, now + 1, sum + a[now], target, path, ans, true);
16             path.pop_back();
17         }
18         help(a, now + 1, sum, target, path, ans, false);
19     }
20     /**
21      * @param num: Given the candidate numbers
22      * @param target: Given the target number
23      * @return: All the combinations that sum to target
24      */
25     vector<vector<int> > combinationSum2(vector<int> &num, int target) {
26         // write your code here
27         sort(num.begin(), num.end());
28         vector<int> path;
29         vector<vector<int> > ans;
30         help(num, 0, 0, target, path, ans, true);
31         return ans;
32     }
33 };
复制代码

 


本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/p/5012822.html,如需转载请自行联系原作者

相关文章
LeetCode 39. Combination Sum
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。
71 0
LeetCode 39. Combination Sum
LeetCode 216. Combination Sum III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
105 0
LeetCode 216. Combination Sum III
|
Go
HDOJ(HDU) 1977 Consecutive sum II(推导、、)
HDOJ(HDU) 1977 Consecutive sum II(推导、、)
106 0
|
算法
[LeetCode]--39. 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 unlimit
1025 0
[LeetCode]--40. Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the
1287 0