Leetcode 39 Solution

This article provides solution to leetcode question 39 (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)


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

        def get_combo(selected, s, i):
            if s == target:

            if i == len(candidates):

            get_combo(selected, s, i + 1)

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

        get_combo([], 0, 0)

        return ans