一个数可以使用多次
图：
节点：x（当前的和，当前要考虑的数a[i]）
边：x->
y1（当前的和，下一个要考虑的数a[i+1]）
y2（当前的和+a[i]，下一个要考虑的数a[i+1]）
BFS
如何求具体解？
队列里放全部的“部分解”——浪费空间
每个节点存放到它的前一个节点——最终还要计算解
DFS
会好一些
leetcode 77，78，90:枚举全部子集
leetcode 51，52:n皇后问题
1 class Solution { 2 public: 3 void help(vector<int> &a, int now, int sum, int target, vector<int> &path, vector<vector<int> > &ans) { 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])) { 14 path.push_back(a[now]); 15 help(a, now, sum + a[now], target, path, ans); 16 path.pop_back(); 17 } 18 help(a, now + 1, sum, target, path, ans); 19 } 20 /** 21 * @param candidates: A list of integers 22 * @param target:An integer 23 * @return: A list of lists of integers 24 */ 25 vector<vector<int> > combinationSum(vector<int> &candidates, int target) { 26 // write your code here 27 sort(candidates.begin(), candidates.end()); 28 vector<int> path; 29 vector<vector<int> > ans; 30 help(candidates, 0, 0, target, path, ans); 31 return ans; 32 } 33 };
本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/p/5012803.html，如需转载请自行联系原作者
