# Leetcode 39 Solution

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 `i`th 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 `i`th element, then the next state will be `(selected, s, i + 1)`.
• Select the `i`th 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`

frame:

## 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
``````