40. 组合总和 II

1.回溯+剪枝

可以先参考[LeetCode 78] 子集和[LeetCode 90]子集 II知道怎么用回溯和去重

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;

class Solution {
  public:
    void helper(vector<vector<int>> &res, vector<int> &candidates, int target,
             vector<int> tmp, int k, int sum) {
        if (sum == target)
            res.push_back(tmp);
        for (int i = k; i < candidates.size(); i++) {
            if (sum + candidates[i] > target)
                continue;
            if (i > k && candidates[i] == candidates[i - 1])
                continue;
            tmp.push_back(candidates[i]);
            helper(res, candidates, target, tmp, i + 1, sum + candidates[i]);
            tmp.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        vector<vector<int>> res;
        vector<int> tmp;
        sort(candidates.begin(), candidates.end());
        helper(res, candidates, target, tmp, 0, 0);
        return res;
    }
};

int main() {
    Solution s;
    vector<int> nums = {10, 1, 2, 7, 6, 1, 5};
    vector<vector<int>> res;
    res = s.combinationSum2(nums, 8);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }

    cout << endl << res.size();

    return 0;
}

2.dfs+集合去重

应该是因为用了set，很慢

class Solution {
  public:
    void dfs(int i, vector<vector<int>> &res, vector<int> &candidates,
             int target, int sum, vector<int> &tmp, set<vector<int>> &res_set) {
        if (i >= candidates.size() || sum > target) {
            return;
        }
        sum += candidates[i];
        tmp.push_back(candidates[i]);
        if (target == sum && res_set.find(tmp) == res_set.end()) {
            res.push_back(tmp);
            res_set.insert(tmp);
        }
        dfs(i + 1, res, candidates, target, sum, tmp, res_set);
        sum -= candidates[i];
        tmp.pop_back();
        dfs(i + 1, res, candidates, target, sum, tmp, res_set);
    }

    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        vector<vector<int>> res;
        vector<int> tmp;
        set<vector<int>> res_set;
        sort(candidates.begin(), candidates.end());
        dfs(0, res, candidates, target, 0, tmp, res_set);
        return res;
    }
};