Description

Submission

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        map<int, int> dict;
        vector<int> sub;
        vector<int> cand;
        for(int i = 0; i < candidates.size(); ++i){
            auto entry = dict.find(candidates[i]);
            if(entry == dict.end()) {
                dict.insert(make_pair(candidates[i], 1));
                cand.push_back(candidates[i]);
            }
            else dict[candidates[i]]++;
        }
        combinationSum2Util(cand, dict, {}, target, res, 0);
        return res;
    }
    
private:
    void combinationSum2Util(vector<int>& candidates, map<int, int>& dict, vector<int> sub, int target, vector<vector<int>>& res, int start_index) {
        for(int i = start_index; i < candidates.size(); ++i) {
            if(dict[candidates[i]] != 0 && target - candidates[i] > 0) {
                dict[candidates[i]]--;
                vector<int> new_sub = sub;
                new_sub.push_back(candidates[i]);
                combinationSum2Util(candidates, dict, new_sub, target - candidates[i], res, i);
                dict[candidates[i]]++;
            }
            if(dict[candidates[i]] != 0 && target - candidates[i] == 0) {
                vector<int> new_sub = sub;
                new_sub.push_back(candidates[i]);
                res.push_back(new_sub);
            }
        }
    }
};