Combination Sum

Problem

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. The same number may be chosen from candidates an unlimited number of times.

Examples

The brute-force approach

Generate all possible combinations using recursion. At each step, try including each candidate (with repeats allowed). Collect combinations that sum to target.

result = []
def backtrack(start, path, remaining):
    if remaining == 0:
        result.append(list(path))
        return
    if remaining < 0:
        return
    for i in range(start, len(candidates)):
        path.append(candidates[i])
        backtrack(i, path, remaining - candidates[i])   # i, not i+1 (allow reuse)
        path.pop()
backtrack(0, [], target)

This is already the standard approach. The key optimization is passing `start` to avoid duplicates (don't go back to earlier candidates).

Spotting the pattern

This is a Backtracking problem. The key question to ask yourself:

Why do you pass `start` (the current index) to the recursive call instead of 0? What would happen if you passed 0 every time?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.