题解 | #加起来和为目标值的组合(二)#

#include <functional>
class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        vector<vector<int> > res;
        vector<int> path;
        vector<int> visited(num.size());
        function<void(int, int)> dfs = [&](int i, int sum) {
            if (sum == 0) {
                res.push_back(path);
                return;
            }
            for (int idx = i; idx < num.size(); ++idx) {
                if (num[idx] > sum) {
                    return;
                }
                if (idx > 0 && num[idx - 1] == num[idx] && !visited[idx - 1]) {
                    continue;
                }
                path.push_back(num[idx]);
                visited[idx] = 1;
                dfs(idx + 1, sum - num[idx]);
                visited[idx] = 0;
                path.pop_back();
            }
        };
        dfs(0, target);
        return res;
    }
};

跟#有重复项数字的全排列 解法是一样的，dfs去重即可。