Q74: Combination Sum. - DSA Patterns (Multi-Lang)

In Simple Words: Backtracking with unlimited reuse: at each index $i$, either choose candidates[i] and recurse at same index $i$ (with target - candidates[i]), or skip to $i + 1$.

Time: $O(2^{\text{target} / \min})$ | Space: $O(\text{target} / \min)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    res = []
    def dfs(i, curr, total):
        if total == target:
            res.append(curr.copy())
            return
        if i >= len(candidates) or total > target:
            return
        # Include candidates[i] (can reuse)
        curr.append(candidates[i])
        dfs(i, curr, total + candidates[i])
        # Skip candidates[i]
        curr.pop()
        dfs(i + 1, curr, total)
    dfs(0, [], 0)
    return res