Combination Sum

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

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may use the same number unlimited times.

1def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
2    res = []
3    cur = []
4    
5    def dfs(i: int, remain: int) -> None:
6        if remain == 0:
7            res.append(cur[:])
8            return
9        if i == len(candidates) or remain < 0:
10            return
11        
12        cur.append(candidates[i])
13        dfs(i, remain - candidates[i])
14        cur.pop()
15        dfs(i + 1, remain)
16    
17    dfs(0, target)
18    return res

Permutations

remain=7

cur=[]

res=[]

Step 1 / 6

Step 1:

Start dfs(i=0, remain=7), cur=[].

Pointers: i=0

Focus: select @ [0]

remain=7