LeetCode: Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

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 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

---

Use Depth-First-Search to find possible solutions.

C++ Code:

/*
 * func: combination_sum_helper
 * goal: helper function to perform a depth first search
 * @param candidates: a set of candidate numbers
 * @param target: target value
 * @param candidate_combination: current possible solution
 * @param result: final solution set
 * return:
 */
void combination_sum_helper(vector<int> candidates, int target, vector<int> candidate_combination, vector<vector<int> >& result){
    if(target == 0){
        result.emplace_back(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, candidates.end());
                candidate_combination.emplace_back(candidates[i]);
                combination_sum_helper(formed_vector, target - candidates[i], candidate_combination, result);
                candidate_combination.pop_back();
            }
        }
    }
}

/*
 * func: combination_sum
 * goal: find all unique combinations where candidate numbers sum to T
 * @param candidates: a set of candidate numbers
 * @param target: target value
 * return: all possible combinations
 */
vector<vector<int> > combination_sum(vector<int> &candidates, int target){
    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);
    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 candidates[i] <= target:
                combination_sum_helper(candidates[i:], target - candidates[i], result, candidate_solution + [candidates[i]])

# func: find all unique combinations in candidate set where the candidate numbers sum to T
# @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