Combinations

Return all possible combinations of k numbers chosen from 1..n.

Why this is worth learning

A start index breaks permutation symmetry. Once a number is chosen, later choices must be larger; [1,3] is generated once and never again as [3,1].

Before coding: one-minute experiment

With n=5, k=3, and prefix [2,4], can the next value be 3? When can the loop stop for a prefix of length 1?

Function signature

func Combine(n, k int) [][]int

Inputs / outputs

• n: upper bound of the range 1..n.
• k: number of elements to choose.
• Return: all size-k combinations, in lexicographic increasing order.

Example

n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Constraints

• 1 <= n <= 20

Core idea (near-solution)

Listing all length-k sequences and rejecting repeats still generates different orders of the same subset. For n=3 and k=2, [1,2] and [2,1] would describe one answer twice. Give every subset a unique increasing representation instead. After choosing i, only values greater than i can follow. That derives the start boundary and makes a result-deduplication set unnecessary.

Backtrack in increasing order. The start index ensures each number is used at most once and combinations stay sorted.

Invariant: path is strictly increasing, and all values are from 1..n.

Algorithm (step-by-step)

1. DFS dfs(start) with a mutable path.
2. If len(path) == k, record a copy and return.
3. For i from start to n:
   • Choose i, recurse with dfs(i+1).
   • Backtrack.
4. (Optional) Prune: if remaining numbers < k - len(path), stop early.

Correctness sketch

The current path is strictly increasing and contains only numbers below start. Choosing i>=start and recursing at i+1 preserves strictness and prohibits reuse. Every size-k subset has a unique increasing representation; following those values in order reaches it exactly once. Iterating candidates ascending gives lexicographic result order. If path length plus the count of available values is less than k, no completion can reach the required size, so pruning that suffix cannot lose a result. Recording a copied path prevents later backtracking from altering earlier combinations.

Trace (hand walkthrough)

Example input:
n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Walk:
- start with 1 -> [1,2],[1,3],[1,4]
- start with 2 -> [2,3],[2,4]
- start with 3 -> [3,4]

Pitfalls to avoid

• Forgetting to backtrack (pop after recursion).
• Not pruning, which can cause unnecessary work.
• Returning combinations in arbitrary order if start is misused.

Debugging lens

Check both row ordering and lexicographic result order, which this contract explicitly requires. Copy each completed path. An i+1 recursion differs from the i recursion used for reusable candidates.

Complexity

• Time: O(C(n, k) * k) to build all results.
• Extra space: O(k) recursion depth (excluding output).

Implementation notes (Go)

• Use a slice path and copy it on output.
• Pruning can be implemented with a simple remaining count check.

Contract precision

For the intended selection problem, 0<=k<=n. The existing implementation also returns one empty combination for k=0 and an empty result for k>n. These behaviors are retained; no negative-k query is specified.

Reconstruction checkpoint

With n=5, k=3, and prefix [2,4], can the next value be 3? When can the loop stop for a prefix of length 1?

Return to Backtracking · Module quiz