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,如需转载请自行联系原作者