Combinations
Medium · Backtracking · Backtracking
Problem
Given two integers n and k, return every way to choose k distinct numbers from 1 to n.
A combination is a set: [1, 2] and [2, 1] are the same combination and must appear only once. Write each combination in increasing order; the combinations themselves may be returned in any order.
Examples
Input: n = 4, k = 3 Output: [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
Choosing 3 of 4 numbers is the same as leaving one out, so there are 4 ways.
Input: n = 2, k = 2 Output: [[1,2]]
The only choice is to take both.
Input: n = 5, k = 2 Output: [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]]
C(5, 2) = 10 pairs.
Constraints
- 1 <= n <= 20
- 1 <= k <= n
Approaches
- Every subset as a bitmask, keep size k — time O(2ⁿ · n), space O(n) beyond the output
Follow-up
Can you produce the combinations one at a time without recursion? Start from [1, 2, ..., k]; to get the next one, find the rightmost position that can still grow, add one to it, and reset everything after it to consecutive values. This walks all C(n, k) combinations in lexicographic order with O(k) memory.
Related problems
Start free on Cariara · Coding problems · System design studio
