LeetCode 40. Combined sum II

Title Description

40. Combinatorial summation II

solution

In fact, this problem can be regarded as a combinatorial problem —— Calculation $candidates$ All and for $target$ Subset , Combination and subset are similar , Before looking at the following code, please understand LeetCode 90. A subset of II

class Solution {
    
public:
    vector<vector<int>> res;

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    
        if (candidates.size() == 0) return res;
        int trackSum = 0;
        vector<int> track;
        sort(candidates.begin(), candidates.end());
        backtrace(candidates, target, 0, track, trackSum);
        return res;
    }

    void backtrace(vector<int>& candidates, int target, int start, vector<int>& track, int trackSum)
    {
    
        if (trackSum == target)
        {
    
            res.push_back(track);
            return;
        }

        if (trackSum > target) return;

        for (int i = start; i < candidates.size(); i++)
        {
    
            if (i > start && candidates[i] == candidates[i - 1]) continue;

            trackSum += candidates[i];
            track.push_back(candidates[i]);
            backtrace(candidates, target, i + 1, track, trackSum);
            trackSum -= candidates[i];
            track.pop_back();
        }
    }
};