LeetCode 39 — Combination Sum

LeetCode #39, Combination Sum, is a classical backtracking problem.

This question is, given an input array with unique numbers called candidates, and an integer called target. We need to find all possible combinations of numbers from candidates that the sum of the numbers in each combination equals to the target.

Take the test case below as an example,

Input: candidates = [2, 3, 7], target = 7
Output: [[2, 2, 3], [7]]
# 2 + 2 + 3 == 7 (target)
# 7 == 7 (target)

Solution: Backtracking

To solve this question, we can use backtracking to go over almost all the combinations formed by candidates. The diagram of backtracking can be found below.

This solution is adding the number from candidates iteratively by recursion. Once, we reach the end that is the sum equals to target or is larger than the target.

If the sum equals to target, we add the current combination to the output. If the sum is larger than the target, we ignore the current combination. When encounter both of these two conditions, we need to return and pop out the last number we added because we know that we already reached the leaf in the diagram.

The key idea is using the combination of a for-loop and recursion as shown below. The start_index indicates the first number to add for the next level to avoid going over duplicated combinations.

def combinationSum(self, candidates, target):
    output = []
    length = len(candidates)
        
    def traverse(comb, start_index):
        if sum(comb) == target:
            output.append(comb[:])
            return
            
        if sum(comb) > target:
            return
            
        for index in range(start_index, length):
            comb.append(candidates[index])
            traverse(comb, index)
            comb.pop()
        
    traverse([], 0)
    return output

Complexity

Time complexity: O(N^((T/M)+1))

1. N is the total number of candidates, T is the target value, and M is the minimal candidates.
2. (T/M + 1) is the maximal height of the tree because the root is the empty combination.
3. The total number of the tree could be up to N^(T/M+1).

We know that the actual number of nodes could be far less than the upper bound by some checking before going to a deeper level.

Space complexity: O(T/M), ignoring the output

The longest path to the leaf is O(T/M). That means the largest list we need to keep is O(T/M). So the space complexity is O(T/M).