40

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> path;
        backtrack(candidates, target, path, 0);
        return res;
    }

    void backtrack(vector<int> &cand, int target, vector<int> &path, int idx){
        if(target == 0){
            res.push_back(path);
            return;
        }
        if(idx >= cand.size())
            return;
        for(int i=idx; i<cand.size(); i++){
            if(i>idx && cand[i-1] == cand[i])
                continue;
            if(cand[i] <= target){
                path.push_back(cand[i]);
                backtrack(cand, target-cand[i], path, i+1);
                path.pop_back();
            }
        }
    }
};