Combination Sum

The problem description can be found in LeetCode.

Approach

This is a classic problem where Backtracking can be applied.

In fact, we can check all possible combination of numbers that will sum up to the target. As soon as our current sum goes below 0, it means that we can discard that path. This is true because all numbers are between 2 and 40.

Solution

from typing import List


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(i: int, amount: int, path: List[int], paths: List[List[int]]) -> None:
            if amount == 0:
                paths.append(path.copy())
                return
            if amount < 0 or i >= len(candidates):
                return

            for j in range(i, len(candidates)):
                path.append(candidates[j])
                dfs(j, amount - candidates[j], path, ans)
                path.pop()

        ans: List[List[int]] = []
        dfs(0, target, [], ans)

        return ans

Complexity

Let's consider the following example:

candidates = [1, 2, 5]
target = 5

This would produce the following space tree:

As for any DFS problem, the space complexity will be proportional with the height of the tree, which can be at most 5, hence $\frac{target}{min(candidates)}$.

Regarding the time complexity, since the maximum height is $\frac{target}{min(candidates)}$, the maximum number of nodes in the tree is $n^{\frac{target}{min(candidates)}+1}$, where $n$ is the size of the candidates list. Plus, we also need to consider the extra work we make to add a solution to the result list, which is $O(\frac{target}{min(candidates)})$.

• Time: $O(n^{M}M)$
• Space: $O(M)$

Where $M$ is $\frac{target}{min(candidates)}$.