Combinations (Push, Recurse, Pop)

core

Implement combinations(n, k) with 1 <= k <= n: return every size-k combination of the values 1 through n, each combination in increasing order, and the combinations themselves in lexicographic order, the order the standard backtracking recursion produces them in.

The drill is the push / recurse / pop trio on one shared path. A single cur list serves every level of the recursion: append the candidate, recurse with the next start value, then pop it off again so the loop can try the next candidate on a clean path. The pop is the line that goes missing, and its absence is invisible at the recording site: the first combination records perfectly, because a path built by pushes alone is correct until the first time the recursion unwinds. From then on cur still carries elements that belong to abandoned branches, the length check stops lining up, and everything after the first recorded combination is missing or garbage. When a backtracking function records one right answer and then goes quiet, look for the pop.

Record a copy of cur when its length reaches k; the shared path keeps mutating after the record, so storing the path itself corrupts earlier answers.

Example: combinations(3, 2) returns {{1, 2}, {1, 3}, {2, 3}}. After recording {1, 2} the recursion pops the 2, tries 3 on the path {1}, records {1, 3}, then pops all the way down and starts again from 2. Without the pops the path after the first record is {1, 2} and grows from there, so no later push ever lands on a clean prefix.

Input format: each test in tests/*.in is laid out as:

Line 1: n k, the two arguments to combinations(n, k).

Test 01.in reads:

1 1

This is n = 1, k = 1: choose 1 number from {1}, so the only combination is {1}.

Where you'll use it:

✦ Solution & editorial unlock with the pass.