Module 16 · Backtracking and Combinatorial Search

153. Choose K Combinations

Foundation · Download this solution · All solutions and shared helpers

Problem

Return all increasing combinations of k distinct integers chosen from 1 through n, in lexicographic order. n and k are nonnegative. Return [[]] for k=0, and [] when k>n. Each answer has exactly k values.

Examples

Example 1

combinations(4,2)
=> [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Increasing choices prevent reorderings of the same combination.

Example 2

combinations(3,0)
=> [[]]

Zero selections form one combination.

Example 3

combinations(2,3)
=> []

There are too few available values.

Reveal the worked solution and reasoning

Why this mechanism works

This is subset generation with a required final length. If need positions remain, choosing a value too close to n leaves too few larger values to finish. Restrict the candidate loop to n-need+1. The pruning follows from a count of available choices, rather than from trial and error.

State and boundaries

path is increasing. start is its next possible value; need=k-len(path) is the number of missing choices.

Protocol

If path has k values, save a copy and return.
Compute need.
Try values start through n-need+1.
Choose, recurse from value+1, then undo.

Visualization

n=4, k=2
first choice <= 4-2+1 = 3
[1] -> [1,2] [1,3] [1,4]
[2] -> [2,3] [2,4]
[3] -> [3,4]

Python implementation

def combinations(n, k):
    output, path = [], []
    def visit(start):
        need = k - len(path)
        if need == 0:
            output.append(path.copy())
            return
        for value in range(start, n - need + 2):
            path.append(value)
            visit(value + 1)
            path.pop()
    visit(1)
    return output

Worked execution

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

combinations(4,2)

L2 combinations: output, path = [], []
n=4; k=2; output=[]; path=[]

L4 visit: need = k - len(path)
start=1; need=2; k=2; n=4; output=[]; path=[]

L8 visit: for value in range(start, n - need + 2):
start=1; need=2; k=2; n=4; output=[]; path=[]; value=1

L9 visit: path.append(value)
start=1; need=2; k=2; n=4; output=[]; path=[1]; value=1

L4 visit: need = k - len(path)
start=2; need=1; k=2; n=4; output=[]; path=[1]

L8 visit: for value in range(start, n - need + 2):
start=2; need=1; k=2; n=4; output=[]; path=[1]; value=2

L9 visit: path.append(value)
start=2; need=1; k=2; n=4; output=[]; path=[1, 2]; value=2

L4 visit: need = k - len(path)
start=3; need=0; k=2; n=4; output=[]; path=[1, 2]

... 42 intermediate state changes omitted ...

L11 visit: path.pop()
start=4; need=1; k=2; n=4; output=[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]; path=[3]; value=4

L10 visit: visit(value + 1)
start=1; need=2; k=2; n=4; output=[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]; path=[3]; value=3

L11 visit: path.pop()
start=1; need=2; k=2; n=4; output=[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]; path=[]; value=3

L12 combinations: visit(1)
n=4; k=2; output=[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]; path=[]

Result: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]. Increasing choices prevent reorderings of the same combination.

combinations(3,0)

L2 combinations: output, path = [], []
n=3; k=0; output=[]; path=[]

L4 visit: need = k - len(path)
start=1; need=0; k=0; n=3; output=[]; path=[]

L6 visit: output.append(path.copy())
start=1; need=0; k=0; n=3; output=[[]]; path=[]

L12 combinations: visit(1)
n=3; k=0; output=[[]]; path=[]

Result: [[]]. Zero selections form one combination.

Why the solution is correct

Increasing choices generate each k-element combination once. The last allowed candidate has exactly need-1 larger values available; every later candidate is impossible. Thus pruning removes no valid answer. Each call either finishes or increases path length and start.

Time and space

O(k*C(n,k)) output-copying work plus the search tree, bounded by O((k+1)*C(n,k)) for 0<=k<=n; O(k) auxiliary depth. k>n returns immediately.

Common mistakes

An exclusive Python range needs stop=n-need+2. Returning [] for k=0 incorrectly removes the unique empty combination.

Reasoning card

State: path is increasing. start is its next possible value; need=k-len(path) is the number of missing choices.

Invariant: Path is strictly increasing and has no repeated choice.

Decision to rehearse: Use a start index and prune when too few candidates remain.

Finish: Choose, recurse from value+1, then undo

Transfer exercise

Return only the count using a recurrence. Explain why enumeration cannot avoid the size of its output.