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

回溯+排序剪枝

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vis.resize(n, false);
        this -> target = target;
        helper(nums, 0, n, 0);
        return res;
    }
    vector<vector<int>> res;
    vector<int> vec;
    vector<bool> vis;
    int target;
    void helper(const vector<int>& nums, int i, int n, int sum){
        if(sum == target){
            res.emplace_back(vec);
            return;
        }
        if(sum > target) return;
        bool isFirst = true;
        int pre;
        for(int j = i; j < n; j ++){
            if(vis[j] || sum + nums[j] > target) continue;
            if(!isFirst){
                if(pre == nums[j]) continue; //同一层不能有相同元素
            }else isFirst = false;
            pre = nums[j];
            sum += nums[j];
            vis[j] = true;
            vec.push_back(nums[j]);
            helper(nums, j + 1, n, sum);
            vec.pop_back();
            vis[j] = false;
            sum -= nums[j];
        }
    }
};