unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 39: Combination Sum

link

Backtracking

For each element x, we take m instances of it such that m \cdot x \le \texttt{rest} and try to make \texttt{rest}-m\cdot x using other elements. We process candidates in a sorted order to be able to use a set to keep only unique combinations.

Recursion tree has height \mathcal{O}(n) and width \mathcal{O}(\texttt{target}). So, time: \mathcal{O}( \texttt{target}^n ), space: \mathcal{O}(n).

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def collect(i, rem):
            if rem == 0:
                return [[]]

            if rem < 0 or i == len(candidates):
                return []

            combs = []
            x = candidates[i]
            j = 0
            while j * x <= rem:
                for c in collect(i+1, rem-j*x):
                    combs.append(c + [x]*j)

                j += 1
            
            return combs

        return collect(0, target)

Dynamic programming

Subproblem

Let C(i, t) be the combinations using elements in nums[0:i+1] and target = t. Then:

C(i, t) = \begin{cases} \left\{ C(i-1, t - m \cdot x_i) + \{ [x_i] \times m \} \ | \ t \ge m \cdot x_i \right\}, & \text{if } i > 0, t > 0 \\ \{ \} & \text{otherwise} \end{cases}

Order

Subproblems are on a n-by-\texttt{target} grid and row-wise processing gives a topological order. However, we use top-down approach with memoization.

Time: \mathcal{O}(n \cdot \texttt{target}^2), space: \mathcal{O}(n \cdot \texttt{target}^2).

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        memo = {}
        def collect(i, rem):
            if rem == 0:
                return [[]]

            if rem < 0 or i == len(candidates):
                return []

            if (key := (i, rem)) in memo:
                return memo[key]

            combs = []
            x = candidates[i]
            j = 0
            while j * x <= rem:
                for c in collect(i+1, rem-j*x):
                    combs.append(c + [x]*j)

                j += 1

            memo[key] = combs
            return combs

        return collect(0, target)

tanvirdotzaman

,

Leave a comment