Leetcode 39 Solution

Leetcode Question Link

https://leetcode.com/problems/combination-sum

Thinking Process

This is a graph search problem. First step is to define states. Our state is defined as (selected, s, i). selected means the candidates we selected. s is the sum of all the current selected candidates. i means ith candidate is the next candidate we are considering to select.

The initial state is ([], 0, 0). For each state, we have two options:

• Not select the ith element, then the next state will be (selected, s, i + 1).
• Select the ith element (if s + candidates[i] <= target), then the next state will be (selected + [candidates[i]], s + candidates[i], i).

Whenever you visit a node with s == target, it means there is a validate selection.

Algorithm Animation

Test case: candidates = [2,3,5], target = 6

Time & Space Complexity

Assuming N is the size of candidates,

• Time complexity: O(2^N)
• Space complexity: O(target)

Solution

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []

        def get_combo(selected, s, i):
            if s == target:
                ans.append(list(selected))
                return

            if i == len(candidates):
                return

            get_combo(selected, s, i + 1)

            if s + candidates[i] <= target:
                selected.append(candidates[i])
                get_combo(selected, s + candidates[i], i)
                selected.pop()

        get_combo([], 0, 0)

        return ans