156. Combination Sum

Why this mechanism works

A sorted choice list makes both deduplication and pruning explicit. Recurse from the same candidate index to allow reuse, while forbidding earlier indices to prevent reordered combinations. Positive values make remaining shrink on every choice; they also justify stopping the loop once a candidate exceeds remaining.

State and boundaries

path is nondecreasing and sums to target-remaining. start is the earliest reusable candidate index.

Protocol

1. Sort distinct candidates.
2. Save path when remaining is zero.
3. Try indices from start.
4. Break when the candidate exceeds remaining.
5. Choose, recurse from the same index with a smaller remainder, then undo.

Visualization

target 7, choices [2,3,6,7]
[2,2] remaining 3 -> choose 3 -> [2,2,3]
[7] remaining 0 -> [7]
larger-than-remaining choices stop the loop

Python implementation

def combination_sum(candidates, target):
    values = sorted(set(candidates))
    output, path = [], []
    def visit(start, remaining):
        if remaining == 0:
            output.append(path.copy())
            return
        for i in range(start, len(values)):
            value = values[i]
            if value > remaining:
                break
            path.append(value)
            visit(i, remaining - value)
            path.pop()
    visit(0, target)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 combination_sum: values = sorted(set(candidates))
candidates=[2, 3, 6, 7]; target=7; values=[2, 3, 6, 7]

L3 combination_sum: output, path = [], []
candidates=[2, 3, 6, 7]; target=7; values=[2, 3, 6, 7]; output=[]; path=[]

L5 visit: if remaining == 0:
start=0; remaining=7; output=[]; path=[]; values=[2, 3, 6, 7]

L8 visit: for i in range(start, len(values)):
start=0; remaining=7; output=[]; path=[]; values=[2, 3, 6, 7]; i=0

L9 visit: value = values[i]
start=0; remaining=7; output=[]; path=[]; values=[2, 3, 6, 7]; i=0; value=2

L12 visit: path.append(value)
start=0; remaining=7; output=[]; path=[2]; values=[2, 3, 6, 7]; i=0; value=2

L5 visit: if remaining == 0:
start=0; remaining=5; output=[]; path=[2]; values=[2, 3, 6, 7]

L8 visit: for i in range(start, len(values)):
start=0; remaining=5; output=[]; path=[2]; values=[2, 3, 6, 7]; i=0

... 57 intermediate state changes omitted ...

L6 visit: output.append(path.copy())
start=3; remaining=0; output=[[2, 2, 3], [7]]; path=[7]; values=[2, 3, 6, 7]

L13 visit: visit(i, remaining - value)
start=0; remaining=7; output=[[2, 2, 3], [7]]; path=[7]; values=[2, 3, 6, 7]; i=3; value=7

L14 visit: path.pop()
start=0; remaining=7; output=[[2, 2, 3], [7]]; path=[]; values=[2, 3, 6, 7]; i=3; value=7

L15 combination_sum: visit(0, target)
candidates=[2, 3, 6, 7]; target=7; values=[2, 3, 6, 7]; output=[[2, 2, 3], [7]]; path=[]

L2 combination_sum: values = sorted(set(candidates))
candidates=[2]; target=3; values=[2]

L3 combination_sum: output, path = [], []
candidates=[2]; target=3; values=[2]; output=[]; path=[]

L5 visit: if remaining == 0:
start=0; remaining=3; output=[]; path=[]; values=[2]

L8 visit: for i in range(start, len(values)):
start=0; remaining=3; output=[]; path=[]; values=[2]; i=0

L9 visit: value = values[i]
start=0; remaining=3; output=[]; path=[]; values=[2]; i=0; value=2

L12 visit: path.append(value)
start=0; remaining=3; output=[]; path=[2]; values=[2]; i=0; value=2

L5 visit: if remaining == 0:
start=0; remaining=1; output=[]; path=[2]; values=[2]

L8 visit: for i in range(start, len(values)):
start=0; remaining=1; output=[]; path=[2]; values=[2]; i=0

L9 visit: value = values[i]
start=0; remaining=1; output=[]; path=[2]; values=[2]; i=0; value=2

L14 visit: path.pop()
start=0; remaining=3; output=[]; path=[]; values=[2]; i=0; value=2

Why the solution is correct

Every emitted path sums to target and has canonical nondecreasing order. Every valid combination can be selected in that order and is explored once. A value larger than remaining and all later values cannot complete a nonnegative remainder. Positive choices guarantee finite depth.

Time and space

Let d=floor(target/min_candidate) and m be distinct candidate count. A coarse time bound is O(m log m + (m+1)^(d+1)*(d+1)); actual work follows visited prefixes and output copies. O(d+m) auxiliary state, excluding output. Empty candidates are constant-search work.

Common mistakes

Zero or negative candidates invalidate the decreasing-remainder termination proof. Advancing to i+1 accidentally prohibits reuse.

Reasoning card

Transfer exercise

Allow each input occurrence only once. Explain both the new start index and the same-depth duplicate skip.