Combinations
Problem Statement
Given two integers n and k, return all possible combinations of k numbers chosen from the range 1 through n. The answer may be returned in any order, but each combination should contain numbers in increasing order conceptually so the same set is not repeated as different permutations.
Input
Two integers: n, the largest available number, and k, the number of values to choose.
Output
A list of combinations, where each combination contains exactly k distinct numbers from 1 through n.
Constraints
- •
1 <= n <= 20 - •
1 <= k <= n
Examples
Example 1
n = 4, k = 2
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]Example 2
n = 1, k = 1
[[1]]Example 3
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]]Learning Objectives
- Recognise a choose-without-order prompt as the combination start-index pattern.
- Carry a **start** value so recursion never revisits earlier numbers or emits permuted duplicates.
- Use remaining-pick pruning to stop branches that cannot reach size **k**.
- Explain why the path is copied only when its size reaches **k**.
Intuition
Pattern Recognition
This is the pure combination pattern: choose k items from an ordered universe, and the order of the chosen items does not matter. That immediately suggests a start index. After choosing number x, future choices must come from numbers greater than x, so [1,2] can be created but [2,1] is never considered.
The state is small: the next number allowed by start and the current path. The base case is when path.size() == k. The key interview insight is that the tree is not a permutation tree; each level only moves forward through the candidate range, which prevents duplicates by construction.
Common mistakes
- ×Restarting the loop from **1** at every depth, which produces permutations such as **[2,1]**.
- ×Adding the same **path** object to the answer instead of adding a copy.
- ×Forgetting to remove the chosen number after the recursive call.
- ×Missing the bound check and exploring branches that do not have enough remaining numbers to fill **k** slots.
Algorithm Explanation
State
Each recursion frame stores start, the smallest number that may still be chosen, and path, the increasing list chosen so far. The remaining picks needed are k - path.size().
Recursion tree
For n = 4, k = 2, depth 0 tries 1, 2, and 3 as first choices. Under 1, the next level tries 2, 3, and 4, producing [1,2], [1,3], and [1,4]. Under 2, it tries 3 and 4, producing [2,3] and [2,4]. Under 3, it tries 4, producing [3,4]. Starting with 4 is pruned because there is no second number left.
Pruning
Before choosing a candidate i, check whether the range i..n has enough numbers to finish the path. If n - i + 1 < k - path.size(), then every later i has even fewer numbers left, so the loop can stop immediately.
Algorithm
- Start DFS with start = 1 and an empty path.
- If path.size() == k, copy path into the answer and return.
- Compute how many more numbers are needed.
- Loop value from start through n, stopping when not enough numbers remain.
- Choose value, recurse with start = value + 1, then unchoose value.
- Return the accumulated combinations.
Solutions
Solution: Start-index DFS with remaining-count pruning
Use the natural ordering 1..n to make every combination increasing. The helper receives the next allowed number, so once a value is chosen it cannot appear again and no earlier value can be permuted in front of it.
Step-by-step
- Create the result list and start DFS at number 1 with an empty path.
- When the path length equals k, append a copy to the result.
- At each frame, compute how many values are still needed.
- Iterate candidate values from start upward while enough numbers remain to complete the path.
- Add the candidate, recurse with candidate + 1, then remove it before trying the next candidate.
O(C(n, k) * k)
O(k)
There are C(n, k) valid leaves and each copied combination has length k. The auxiliary recursion depth is k, excluding the output.
Java implementation
Dry Run
Sample input
n = 4, k = 2. Track how start forces increasing choices and how the last impossible first choice is pruned.
| depth | start | choice | path and count | action |
|---|---|---|---|---|
| 0 | 1 | 1 | [1] size 1 | choose 1, recurse with start 2 |
| 1 | 2 | 2 | [1,2] size 2 | size is k, add copy |
| 1 | 2 | 3 | [1,3] size 2 | size is k, add copy |
| 1 | 2 | 4 | [1,4] size 2 | size is k, add copy |
| 0 | 1 | 2 | [2] size 1 | choose 2, recurse with start 3 |
| 1 | 3 | 3 | [2,3] size 2 | size is k, add copy |
| 1 | 3 | 4 | [2,4] size 2 | size is k, add copy |
| 0 | 1 | 3 | [3] size 1 | choose 3, recurse with start 4 |
| 1 | 4 | 4 | [3,4] size 2 | size is k, add copy |
| 0 | 1 | 4 | [] size 0 | prune because only one number remains but two are needed |
The DFS emits each increasing pair once. The branch starting with 4 is skipped because it cannot be completed to length 2.
Interview Tips
Say early that combinations are not permutations. The start index is the proof: every recursive child can only choose numbers to the right of the current choice. Then add the remaining-count bound because it shows you are thinking about the shape of the recursion tree, not just writing a template.
Likely follow-ups
- How would you generate combinations in lexicographic order?
- How would you return only the count without listing every combination?
- How would the template change if the input numbers contained duplicates?
- How would you choose **k** items from an arbitrary array instead of **1..n**?
Similar Problems
Key Takeaways
- A start index is the core tool for choosing without order.
- Moving to **value + 1** prevents reuse and prevents permuted duplicates.
- Prune when the remaining range cannot fill the remaining slots.
- Copy the path only at valid leaves of size **k**.