LintCode: Combination Sum

清疚 2021-09-19 09:46 199阅读 0赞

一个数可以使用多次

图：

节点：x（当前的和，当前要考虑的数a\[i\]）

边：x->

y1（当前的和，下一个要考虑的数a\[i+1\]）

y2（当前的和+a\[i\]，下一个要考虑的数a\[i+1\]）

BFS

如何求具体解？

队列里放全部的“部分解”——浪费空间

每个节点存放到它的前一个节点——最终还要计算解

DFS

会好一些

leetcode 77，78，90:枚举全部子集

leetcode 51，52:n皇后问题

![复制代码][copycode.gif]

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 };

![复制代码][copycode.gif]

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

[copycode.gif]: /images/20210726/f6e195a2171746bb9c4b0938a162cc0f.png