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

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