77. Combinations
Given two integers n and k, produce every way of choosing k distinct numbers from 1 through n.
Return the result as a list of lists in canonical form so the output is deterministic: each combination is written with its numbers in increasing order, and the combinations themselves appear in lexicographic order. For n = 4, k = 2 the sequence runs [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4].
There are C(n, k) combinations in total — aim for a solution whose work is proportional to the output it builds.
Example 1:
Input: n = 4, k = 2
Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Explanation: All 6 ways to pick 2 numbers out of {1, 2, 3, 4}, listed lexicographically.
Example 2:
Input: n = 1, k = 1
Output: [[1]]
Explanation: Choosing 1 number out of {1} leaves a single combination.
Constraints:
- 1 ≤ n ≤ 15
- 1 ≤ k ≤ n
Hints:
Build a combination one number at a time. If the last number placed is x, the next one may only come from x+1..n — that single rule enforces increasing order and rules out duplicates.
Recursion shape: choose(start) tries each candidate x in start..n, appends it, recurses with choose(x + 1), then removes it (backtracks). Emitting a copy whenever the path reaches length k yields lexicographic order for free.
Prune dead branches: with `r` slots still to fill, a candidate x only works if there are at least r numbers left in x..n, i.e. x <= n - r + 1. With this bound the search does work proportional to C(n, k).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 4, k = 2
Expected output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]