LeetCode 39 Combination Sums

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.
• 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]
]

Difficulty
Medium

Related Problems

[LeetCode 40] Combination Sums II

Analysis

While iterating over the given numbers, we push the current candidate number into an auxiliary container until we reach the point that only one number need to be find in order to match the sum to the target value. If in the remaining numbers, we can not find such a number, we pop one out from out auxiliary container, pop in the next number, and continue our algorithm. When we find a solution, we pop out some numbers, and continue to find the next solution. Obviously, this is a backtrack problem.

Make sure the array is sorted before we use the backtrack algorithm.

1. Cpp solution 16ms

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        vector<vector<int>> result;
        vector<int> sol;
        sort(candidates.begin(), candidates.end());
        combinationSum(candidates, 0, target, sol, result);
        return result;
    }

    void combinationSum(vector<int> &candidates, int start, int target, 
        vector<int> &sol, vector<vector<int>> &res){
        if(target == 0){
            res.push_back(sol);
            return;
        }
        for(int i = start; i < (int)candidates.size() && target >= candidates[i]; ++i){
            sol.push_back(candidates[i]);
            combinationSum(candidates, i, target - candidates[i], sol, res);
            sol.pop_back();
        }
    }
};

1. Go solution

Note
In Go, don't append a will-modified slice to another slice, we shoulde deep copy, e.g. use this: *all = append(*all, append([]int(nil), *sol...))

Also, since we can use the same element multiple times, we use i instead of i + 1 in each iteration.

func combinationSum(candidates []int, target int) [][]int {
    all := [][]int{}
    sol := []int{}
    sort.Ints(candidates)
    combHelper(candidates, &sol, 0, target, &all)
    return all
}

func combHelper(candidates []int, sol *[]int, start, target int, all *[][]int) {
    if target == 0 {
        *all = append(*all, append([]int(nil), *sol...))
        return
    }

    for i := start; i < len(candidates) && target >= candidates[i]; i++ {
        *sol = append(*sol, candidates[i])
        combHelper(candidates, sol, i, target-candidates[i], all) 
        *sol = (*sol)[0 : len(*sol)-1]
    }
}

Reference