LeetCode: Combination Sum II

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 (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

---

We can use the same idea as the previous one to solve this problem. Just to remind, if the current candidate number is equal to the previous one, then we can skip to eliminate duplicate solutions. For C++, I chose to use a different way. I use unordered_set to remove duplicate solutions from final sets. In this case we have to write our own hash functional class and equal functional class.

C++ Code:

//Hash functional class for unordered_set
class HashVector{
public:
    const size_t operator()(const vector<int>& vec) const{
        int value = 0;
        for(const auto &it: vec)
            value ^= it;
        return static_cast<size_t>(value);
    }
};
//Equal functional class for unordered_set
class EqualVector{
public:
    const bool operator()(const vector<int>& left, const vector<int> &right) const{
        if(left.size() != right.size()){
            return false;
        }
        for(int i=0; i<left.size(); i++){
            if(left[i] != right[i]){
                return false;
            }
        }
        return true;
    }
};
//helper function for combination sum
void combination_sum_helper(vector<int> candidates, int target, vector<int> candidate_combination, unordered_set<vector<int>, HashVector, EqualVector>& result){
    if(target == 0){
        result.emplace(candidate_combination);
        return;
    }
    else if(target < 0){
        return;
    }else{
        for(int i = 0; i < candidates.size(); ++i){
            if(candidates[i] <= target){
                vector<int> formed_vector(candidates.begin()+i+1, candidates.end());
                candidate_combination.emplace_back(candidates[i]);
                combination_sum_helper(formed_vector, target - candidates[i], candidate_combination, result);
                candidate_combination.pop_back();
            }
        }
    }
}
vector<vector<int> > combination_sum_ii(vector<int> &candidates, int target) {
    unordered_set<vector<int>, HashVector, EqualVector> result_set;
    vector<vector<int> > result;
    sort(candidates.begin(), candidates.end());
    if(candidates.size() == 0 || candidates[0] > target){
        return result;
    }
    vector<int> candidate_combination;
    combination_sum_helper(candidates, target, candidate_combination, result_set);
    for(const auto &it : result_set)
        result.emplace_back(it);
    return result;
}

Python Code:

# func: helper function for combination sum
# @param candidates: candidates numbers
# @param target: target value
# @param result: final result set
# @param candidate_solution: current solution list
# @return:
def combination_sum_helper(candidates, target, result, candidate_solution):
    if target == 0:
        result.append(candidate_solution)
    elif target < 0:
        return
    else:
        for i in xrange(len(candidates)):
            if i > 0 and candidates[i] == candidates[i-1]:
                continue
            if candidates[i] <= target:
                combination_sum_helper(candidates[i+1:], target - candidates[i], result, candidate_solution + [candidates[i]])


# func: find all unique combinations in candidate set where the candidate numbers sum to T
#       each number may only be used once in the combination
# @param candidates: candidate set
# @param target: the target value
# @return: a list of lists of numbers
def combination_sum(candidates, target):
    candidates.sort()
    if len(candidates) == 0 or candidates[0] > target:
        return []
    result = []
    combination_sum_helper(candidates, target, result, [])

    return result