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.

Candidates and target are positive integers.

02 · Analysis

Candidates are distinct positive integers and target is positive. Taking a candidate keeps the same index so it may be reused; skipping moves to the next index, which prevents order-only duplicate combinations. Stop at remaining==0 or when no candidates remain. If the minimum candidate is c, at most floor(target/c) values fit in a path; the search is exponential in the number of choices and depth, with auxiliary space bounded by candidate count plus that depth. Include copied answers separately.

03 · 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