跳转至

39 组合总和II

class Solution {
private:
    vector<int> res;
    vector<vector<int>> ans;
    void dfs(const vector<int>& candidates, vector<int>& res, int target,
             int index) {
        if (index == candidates.size()) {
            return;
        }
        if (target == 0) {
            ans.push_back(res);
            return;
        }
        // 不选这个数
        dfs(candidates, res, target, index + 1);
        // 选这个数
        if (candidates[index] <= target) {
            res.push_back(candidates[index]);
            dfs(candidates, res, target - candidates[index], index);
            res.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, res, target, 0);
        return ans;
    }
};