LeetCode 40. 组合总和 II

题目描述

40. 组合总和 II

解法

其实这道题可以看成一个组合问题——计算 $candidates$ 中所有和为 $target$ 的子集，组合和子集其实是类似的，在看下面代码之前不放先理解一下 LeetCode 90. 子集 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();
        }
    }
};