DSA problem
Combinations
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. The answer may be returned in any order. The total number of combinations is the binomial coefficient C(n, k) = n! / (k! * (n - k)!), which can be very large but is always smaller than 2^n.
The unsophisticated approach is to enumerate every subset of {1, …, n} and keep only those of size exactly k. That works but generates 2^n subsets, the vast majority of which the wrong size. A direct backtracking algorithm produces exactly C(n, k) combinations with no waste, by always advancing the index forward and stopping the loop as soon as too few candidates remain.
The recursive routine backtrack(start) operates on a growing path. When path.length == k we snapshot a copy and return. Otherwise we iterate i from start to n, pick i, recurse with start = i + 1 (so each number is used at most once and combinations are produced in increasing index order), then un-pick.
The most important optimization is the loop upper-bound prune: once fewer than k - path.length candidates remain after i, the branch cannot complete. We tighten the upper bound to i <= n - (k - path.length) + 1. With this prune, we never enter a dead-end branch, so the number of recursive calls is exactly the number of internal nodes in the combinations tree, giving optimal O(k * C(n, k)) total time and O(k) working space.
Examples
n = 4, k = 2[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]n = 1, k = 1[[1]]n = 5, k = 3[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]Constraints
- 1 <= n <= 20
- 1 <= k <= n
- The answer may be returned in any order.
- No duplicates are allowed in the output.
- Each returned combination contains exactly `k` distinct integers.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.