Combination Sum

01 · Question

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.

02 · Solution

Reference solution

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