#77 Combinations
the problem
In plain words
Given two integers n and k, return every way to pick k different numbers from 1 to n. A combination is a set: [1, 2] and [2, 1] are the same combination, so list it only once. Any order is fine.
in n = 4, k = 2
out [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
C(4, 2) = 6 ways.
in n = 1, k = 1
out [[1]]
- 1 ≤ n ≤ 20
- 1 ≤ k ≤ n
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBacktracking: combinations & partitions
Pick numbers in increasing order: after x, only numbers bigger than x may follow, so every set is built once. And stop the loop early when too few numbers are left to reach k.
solutions
From brute force to optimal
Every subset of 1..n is a number from 0 to 2ⁿ − 1. Keep the masks with exactly k one-bits.
- For mask in 0 .. 2ⁿ − 1:
- skip it unless
Integer.bitCount(mask) == k; - otherwise list the numbers i + 1 whose bit i is on.
All 2ⁿ masks are looked at (each bitCount is O(1)); only the C(n, k) good ones pay O(n) to build a list.
One list under construction (excluding the output).
class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> result = new ArrayList<>(); for (int mask = 0; mask < (1 << n); mask++) { // every subset of 1..n if (Integer.bitCount(mask) != k) continue; // keep only the ones of size k List<Integer> combo = new ArrayList<>(); for (int i = 0; i < n; i++) { if ((mask & (1 << i)) != 0) combo.add(i + 1); // bit i on → number i + 1 is in } result.add(combo); } return result; }}Walk 1..n. For each number, first take it, then skip it. Record when k numbers are taken.
- path.size() == k → record a copy.
- x > n → dead end, return.
- Take x: recurse on x + 1, then undo.
- Skip x: recurse on x + 1.
Up to about 2ⁿ⁺¹ calls: branches keep going even when too few numbers are left to reach k.
Recursion depth is up to n (excluding the output).
class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> result = new ArrayList<>(); dfs(1, n, k, new ArrayList<>(), result); return result; } private void dfs(int x, int n, int k, List<Integer> path, List<List<Integer>> result) { if (path.size() == k) { // k numbers picked → one answer result.add(new ArrayList<>(path)); return; } if (x > n) return; // no numbers left to decide on path.add(x); // take x dfs(x + 1, n, k, path, result); path.remove(path.size() - 1); // undo dfs(x + 1, n, k, path, result); // skip x }}The template: for x from start to n − need + 1, choose x, explore with x + 1, un-choose.
- path.size() == k → record a copy, return.
- need = k − path.size().
- For x from start to n − need + 1: path.add(x); backtrack(x + 1); path.remove(last).
Every node now leads to at least one answer, so there are at most (k + 1)·C(n, k) nodes, and each answer is copied in O(k).
The path and the recursion are at most k deep (excluding the output).
class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> result = new ArrayList<>(); backtrack(1, n, k, new ArrayList<>(), result); return result; } private void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> result) { if (path.size() == k) { // goal: k numbers chosen result.add(new ArrayList<>(path)); // record a COPY return; } int need = k - path.size(); // numbers still to pick for (int x = start; x <= n - need + 1; x++) { // stop while enough numbers remain path.add(x); // choose backtrack(x + 1, n, k, path, result); // explore: only larger numbers next path.remove(path.size() - 1); // un-choose } }}Dry run
in the room
How to say it in the interview
talk track
- "This is Subsets with a size limit: k of n, and order doesn't matter."
- "I pick numbers in increasing order, so each set is built once — no Set needed."
- "If fewer than
neednumbers are left, the branch can't finish, so the loop stops at n − need + 1." - Cost: C(n, k) answers × O(k) to copy each. The output itself is that big, so this is optimal.
traps
- Looping from 1 instead of
start: [1, 2] and [2, 1] both appear. result.add(path)without copying: every entry ends up as the same empty list.- Off by one in the bound: it is
x <= n - need + 1, inclusive.
what they ask next
Follow-ups
Only count them?
No search needed: C(n, k) = n! / (k!·(n − k)!), or Pascal's rule C(n, k) = C(n − 1, k − 1) + C(n − 1, k) as a small DP.
Combination Sum III (LC 216): k numbers from 1–9 that add up to n?
Same template with a running sum. Record when size == k and sum == n; break as soon as the sum passes n.
before you submit
Edge cases to test
- k = n → exactly one combination: [1, 2, …, n].
- k = 1 → n lists with one number each.
- n = 20, k = 10 → 184,756 combinations: the output alone is huge, so no wasted branches.
practise next
Similar problems
- #78SubsetsMediumin Backtracking
- #39Combination SumMediumin Backtracking
- #46PermutationsMediumin Backtracking