We need to generate all possible ways to pick k numbers from the integers 1 through n, where order does not matter. This is the classic "n choose k" problem from combinatorics.

Unlike permutations, order does not matter. Picking [1, 3] is the same as picking [3, 1], so only one of them should appear in the output. We need a systematic way to explore choices without producing the same combination twice in different orders.

Picking numbers in increasing order solves this. If we have already picked the number 3, we only consider numbers greater than 3 for the next pick. Every combination is then generated exactly once, in sorted form.

Key Constraints:

Intuition

For a fixed k, nested loops generate every combination. With k = 2, an outer loop picks the first number and an inner loop picks the second, starting one past the first so the picks stay in increasing order. With k = 3 you would add a third loop, and so on. The pattern breaks down because k is an input: it can be anything from 1 to 20, and you cannot write a variable number of loops.

Recursion fixes this. Each recursive call plays the role of one loop level. The call receives a start value, loops i from start to n, appends i to the combination under construction, and recurses with start = i + 1 to fill the next slot. When the combination reaches length k, it is copied into the result. This enumerates the same sequences as the nested loops, for any k.

The cost of this direct translation is wasted work. The recursion enters branches that cannot produce a complete combination. With n = 4 and k = 2, picking 4 first leaves no numbers for the second slot, yet the call is still made and returns without recording anything. Approach 2 removes these dead ends.

Algorithm

Example Walkthrough

Input:

The recursion with n = 4 and k = 2 runs as follows:

All branches are exhausted and the function returns six combinations:

Code

The wasted calls are predictable in advance: a branch cannot complete once fewer numbers remain than slots to fill. The next approach checks this condition before recursing.

Intuition

The structure is the same as Approach 1: pick a number, recurse to fill the remaining slots, then remove it and try the next option, always picking in increasing order so no combination appears twice.

The improvement is the loop bound. Instead of letting i run all the way to n, stop it at n - remaining + 1, where remaining is the number of slots still to fill. Any value past that bound starts a branch that cannot finish.

Algorithm

Example Walkthrough

Code

Recursion is not the only way to enumerate combinations. Each subset of {1, ..., n} can be encoded as an n-bit integer, which turns the whole problem into a single loop over bitmasks.

Intuition

Each combination of k numbers from {1, 2, ..., n} can be represented as a bitmask of length n, where the i-th bit is 1 if number (i+1) is included. For example, with n = 4 and k = 2, bitmask 0011 represents {1, 2} and 0101 represents {1, 3}.

Subsets and masks correspond one to one, so the problem reduces to enumerating every n-bit integer with exactly k set bits: iterate from 0 to 2^n - 1, keep the masks whose set-bit count equals k, and decode each one into a combination. Every combination appears exactly once, with no recursion and no duplicate handling. Because masks are visited in numeric order, the output order differs from the backtracking approaches ([2,3] is produced before [1,4]); the problem accepts any order.

The loop scans all 2^n masks regardless of k, so this does more work than pruned backtracking whenever C(n, k) is small. With n capped at 20, that is about a million masks, well within the limits here.

Algorithm

Example Walkthrough

Code