#77
Combinations
Medium Backtracking with pruning
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return all ways to choose k numbers from 1..n (order doesn't matter).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: all ways to choose k numbers from 1..n.
Why this works: pick in increasing order so each set appears once; stop early when not enough numbers remain.
Example: n = 4, k = 2
[1,2] [1,3] [1,4] [2,3] [2,4] [3,4]✦Hints open one at a time
Pick numbers in increasing order so each combination is built once.
Prune: if not enough numbers remain to reach size k, stop.
↗Approach
backtrack(start): if the path has k numbers, record it. Otherwise try i from start up to n − (k − size) + 1, which is the last start that can still fill the path.
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
backtrack(n, k, 1, new ArrayList<>(), res);
return res;
}
private void backtrack(int n, int k, int start, List<Integer> path, List<List<Integer>> res) {
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i <= n - (k - path.size()) + 1; i++) { // enough numbers left?
path.add(i);
backtrack(n, k, i + 1, path, res);
path.remove(path.size() - 1);
}
}
}!Common mistake
No pruning — still correct, but explores many dead branches.
Complexity
- Time: O(k · C(n, k)).
- Space: O(k).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon