Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie,…

leetcode_combination_sums_2.cpp

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int> > ans;
        map<vector<int>, bool> hash;
        if (target == 0 || num.empty())
            return ans;
        vector<int> tmp;
        sort(num.begin(), num.end());
        for (int i = 0; i < num.size(); ++i) {
            if (target > num[i]) {
                vector<vector<int> > t = combinationSum2(tmp, target - num[i]);
                for (int j = 0; j < t.size(); ++j) {
                    t[j].push_back(num[i]);
                    hash[t[j]] = true;
                }
            }
            else if (target == num[i]) {
                vector<int> k;
                k.push_back(num[i]);
                hash[k] = true;
            }
            else
                break;
            tmp.push_back(num[i]);
        }
        for (map<vector<int>, bool>::iterator it = hash.begin(); it != hash.end(); ++it)
            ans.push_back(it->first);
        return ans;
    }
};