LeetCode 39. Combination Sum

07 Aug 2018

Description:

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

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

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example:

input:

candidates = [2,3,6,7], target = 7

output:

[ [7], [2,2,3] ]

input:

candidates = [2,3,5], target = 8

output:

[ [2,2,2,2], [2,3,3], [3,5] ]

Solution:

class Guess:
    numList = None
    sum = 0
    index = 0

    def __init__(self, obj=None, sum=0, index = 0):
        if obj is None:
            self.numList = []
        else:
            self.numList = copy.deepcopy(obj)
        self.sum = sum
        self.index = index

class Solution:

    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        queue = []
        for ind, item in enumerate(candidates):
            newGuess = Guess([item], item, ind)
            queue.append(newGuess)

        result = []

        while len(queue) > 0:
            front = queue.pop(0)
            if front.sum == target:
                result.append(front.numList)
            elif front.sum < target:
                for index in range(front.index, len(candidates)):
                    newGuess = Guess(front.numList, front.sum, index)
                    newGuess.numList.append(candidates[index])
                    newGuess.sum += candidates[index]
                    queue.append(newGuess)

        return result

class Solution {
public:
    
    struct Guess{
        vector<int> nums;
        int sum;
        int index;
    };
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
        queue<Guess> myQueue;
        for(auto i = 0U; i < candidates.size(); ++i){
            Guess guess;
            guess.nums.push_back(candidates[i]);
            guess.sum = candidates[i];
            guess.index = i;
            myQueue.push(move(guess));
        }
        
        vector<vector<int>> result;
        int candidateSize = candidates.size();
        
        while(!myQueue.empty()){
            auto front = move(myQueue.front());
            myQueue.pop();
            
            if(front.sum == target){
                result.emplace_back(move(front.nums));
            }
            else if(front.sum < target){
                for(auto i = front.index; i < candidateSize; ++i){
                    Guess guess;
                    guess.nums.resize(front.nums.size() + 1);
                    copy(front.nums.begin(), front.nums.end(), guess.nums.begin());
                    guess.nums.back() = candidates[i];
                    guess.sum = front.sum + candidates[i];
                    guess.index = i;
                    myQueue.push(move(guess));
                }
            }
        }
        
        return result;
    }
};

This problem can be solved with backtracking/DFS methods. I am using a non-recursive DFS to solve the problem, note that every time when we enter the next level of searching, we only select the candidates whose index is greater or equal to index, and this will ensure that our choice of numbers is unique.

The Python solution takes around 740ms, and the C++ solution takes around 16ms. Both solutions are slow, because compared to recursive approach, the non-recursive one needs to allocate space, construct object and copy array, which can result in great overhead.

Alan Xiang's Blog

LeetCode 39. Combination Sum

Description:

Note:

Example:

Solution: