Leetcode 39 Solution
This article provides solution to leetcode question 39 (combination-sum)
Access this page by simply typing in "lcs 39" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
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.
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.
candidates = [2,3,5], target = 6
Time & Space Complexity
N is the size of
- Time complexity:
- Space complexity:
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