Combinations (LeetCode 77)
What a combination is (assume nothing): a combination is a group of numbers where only which numbers are in the group matters, not their order. [1, 3] and [3, 1] are the same combination.
You get two integers n and k. Using the numbers 1 to n, list every group of exactly k different numbers. Each group appears once, and the groups can be returned in any order.
Worked Examples
n = 4, k = 2[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]n = 1, k = 1[[1]]⚖️Formal Constraints & Bounds
1 <= n <= 201 <= k <= n
Core Insight
Recursing with i + 1 means every group is built in increasing order, so each group is produced exactly once and no number repeats inside it. Recording only when len(path) == k (and returning right away) is the single change that turns the Subsets search into a fixed-size Combinations search.
Real-World Scenario & Production Applications
Picking every possible team of k people from a group of n, every set of k features to test together, or every k-item bundle from a catalog all mean listing each fixed-size group exactly once, without repeating the same group in a different order.
Subproblems & Recurrence Decomposition3 Phases
At each level, try only numbers from start to n. Anything below start was already passed over, which keeps every group in increasing order.
for i in range(start, n + 1):Step-by-Step Execution Trace Table
[ ] (start=1) / | \ \ choose 1 choose 2 choose 3 choose 4 / | \ \ [1] (start=2) [2] (start=3) [3] (start=4) [4] (start=5) / | \ / \ | (no numbers left) [1,2] [1,3] [1,4] [2,3] [2,4] [3,4] ✅ ✅ ✅ ✅ ✅ ✅ (len(path) == k = 2: RECORD) Step-by-Step Decision Trace
- Step 1 (Root, start=1):
path = [], size 0 < 2. Try numbers 1 to 4. - Step 2 (Choose 1):
path = [1], recurse withstart = 2. - Step 3 (Choose 2):
path = [1, 2]. Size is 2 Record[1, 2]✅ and return. - Step 4 (Pop 2, choose 3):
path = [1, 3]Record[1, 3]✅. - Step 5 (Pop 3, choose 4):
path = [1, 4]Record[1, 4]✅. The loop at[1]ends. - Step 6 (Pop 1, choose 2 at the root):
path = [2], recurse withstart = 3. Record[2, 3]✅ and[2, 4]✅. - Step 7 (Choose 3 at the root):
path = [3], recurse withstart = 4. Record[3, 4]✅. - Step 8 (Choose 4 at the root):
path = [4], recurse withstart = 5. No numbers are left, so this branch records nothing. Search Complete: Output[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], which is groups.
n = 4, k = 2Expected:[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]| 1 | results, path = [], [] |
| 2 | def backtrack(start): |
| 3 | if len(path) == k: |
| 4 | results.append(list(path)) |
| 5 | return |
| 6 | need = k - len(path) |
| 7 | for i in range(start, n - need + 2): |
| 8 | path.append(i) |
| 9 | backtrack(i + 1) |
| 10 | path.pop() |
| 11 | backtrack(1) |
| 12 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Subsets record a group at every node of the decision tree, so you get every size from empty to full. Combinations ask for groups of one fixed size k. The loop and the i + 1 are exactly the same as in Subsets; the only change is when you record: only once len(path) == k, and then you stop going deeper.
🏀 The Analogy: Picking a Team of k Players
Think of n players with jersey numbers 1 to n, and you must list every possible team of k. To avoid writing the same team twice, always list a team's jerseys from smallest to largest. So after you pick jersey 3, you only look at jerseys 4 and up. The team [1, 3] gets written once; [3, 1] never appears, because nobody ever looks backward. As soon as a team has k players, write it down and step back to try the next player.
🔑 The Key Idea in the Code
backtrack(i + 1) does two jobs at once: it keeps i from being used twice in the same group, and it makes every group appear in increasing order only, so no group is ever listed twice.
✂️ The Loop Bound: Stop When There Aren't Enough Numbers Left
If the group still needs need = k - len(path) numbers, starting at a number too close to n can never fill it. The largest useful start is n - need + 1, so the loop is for i in range(start, n - need + 2). The answer is the same as looping up to n; the dead-end branches are simply never entered. Cut the bound one lower and every group that ends in n is lost.
Recording before the group is full: Recording at every node (the Subsets habit) returns groups of every size. Record only when
len(path) == k, andreturnright after, because a full group can't grow.Looping from 0 instead of
start: Starting each loop at the first number builds[1, 2]and[2, 1]as two different groups. Always loop fromstartand recurse withi + 1.Appending the live
path:results.append(path)stores a reference to the one shared list, which is empty when the search ends. Appendlist(path).Off-by-one in the pruning bound: The optional early stop allows
iup ton - (k - len(path)) + 1inclusive, so the range end isn - (k - len(path)) + 2. One less skips valid groups.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Return all combinations of k numbers" + "order does not matter" + small n (n <= 20) + a fixed group size k.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: path is always an increasing list of numbers from 1..n, and every number after path[-1] is still available. Complete when len(path) == k: record a copy and return, since a full group can't grow.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Recursing with
start + 1instead ofi + 1-- the next level then restarts too early, so a number can repeat ([2, 2]) and the same group appears in two orders ([2, 3]and[3, 2]).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Combinations. I build each group in increasing order with backtrack(start): the loop tries every number i from start upward, appends it to path, recurses, then pops it. A group of numbers has exactly one increasing order, so building only in that order produces each group once and never both [1, 2] and [2, 1]. When path has k numbers I save a copy and return. I also stop the loop early when too few numbers are left to fill the group, which removes dead branches without changing the answer. The trap is the recursive call: it must be backtrack(i + 1), not backtrack(start + 1), because the next pick has to come after the number I just picked; with start + 1 and n = 4, k = 2, I get [3, 2] next to [2, 3]. There are C(n, k) groups and each copy costs k, so it's O(k times C(n, k)) time and
O(k)extra space for path and the recursion."
Complexity & Mathematical Proof
O(k · C(n, k))
Look at the execution steps: the search records exactly C(n, k) groups, and copying each one with list(path) costs k. The internal nodes of the tree are prefixes of those groups, so the total work is O(k · C(n, k)).
O(k) Call Stack
The recursion never goes deeper than k levels, and path holds at most k numbers. The output itself holds C(n, k) groups of k numbers each.
Derivation Progression
Leaves = C(n, k)
Every recorded group is one leaf of the tree, and each group is produced exactly once.
Max Depth = k
A group is recorded (and the branch stops) as soon as it has k numbers.
k per recorded group
list(path) copies k numbers each time a group is recorded.
Variable Definitions
Largest number available (choose from 1..n)
Size of each group
Memory Architecture & Bounds
O(k) Call stack depth
O(k) Current group (path)
O(k · C(n, k)) Result groups
Boundary Best / Worst Cases
when or .
.
, largest when .
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "all possible combinations of k numbers from [1, n]", "order does not matter". Canonical combinations pattern: keep the candidate index strictly increasing so no group is built twice.
. Output size is , at most groups; the output, not the search, sets the cost.
At scale memory fails first: groups of numbers each. When the caller only iterates (for example, feeding each group to a job), stream the groups with a generator and yield a copy of path.
Combinations (LeetCode 77)
What a combination is (assume nothing): a combination is a group of numbers where only which numbers are in the group matters, not their order. [1, 3] and [3, 1] are the same combination.
You get two integers n and k. Using the numbers 1 to n, list every group of exactly k different numbers. Each group appears once, and the groups can be returned in any order.
Worked Examples
n = 4, k = 2[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]n = 1, k = 1[[1]]⚖️Formal Constraints & Bounds
1 <= n <= 201 <= k <= n
Core Insight
Recursing with i + 1 means every group is built in increasing order, so each group is produced exactly once and no number repeats inside it. Recording only when len(path) == k (and returning right away) is the single change that turns the Subsets search into a fixed-size Combinations search.
Real-World Scenario & Production Applications
Picking every possible team of k people from a group of n, every set of k features to test together, or every k-item bundle from a catalog all mean listing each fixed-size group exactly once, without repeating the same group in a different order.
Subproblems & Recurrence Decomposition3 Phases
At each level, try only numbers from start to n. Anything below start was already passed over, which keeps every group in increasing order.
for i in range(start, n + 1):Step-by-Step Execution Trace Table
[ ] (start=1) / | \ \ choose 1 choose 2 choose 3 choose 4 / | \ \ [1] (start=2) [2] (start=3) [3] (start=4) [4] (start=5) / | \ / \ | (no numbers left) [1,2] [1,3] [1,4] [2,3] [2,4] [3,4] ✅ ✅ ✅ ✅ ✅ ✅ (len(path) == k = 2: RECORD) Step-by-Step Decision Trace
- Step 1 (Root, start=1):
path = [], size 0 < 2. Try numbers 1 to 4. - Step 2 (Choose 1):
path = [1], recurse withstart = 2. - Step 3 (Choose 2):
path = [1, 2]. Size is 2 Record[1, 2]✅ and return. - Step 4 (Pop 2, choose 3):
path = [1, 3]Record[1, 3]✅. - Step 5 (Pop 3, choose 4):
path = [1, 4]Record[1, 4]✅. The loop at[1]ends. - Step 6 (Pop 1, choose 2 at the root):
path = [2], recurse withstart = 3. Record[2, 3]✅ and[2, 4]✅. - Step 7 (Choose 3 at the root):
path = [3], recurse withstart = 4. Record[3, 4]✅. - Step 8 (Choose 4 at the root):
path = [4], recurse withstart = 5. No numbers are left, so this branch records nothing. Search Complete: Output[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], which is groups.
n = 4, k = 2Expected:[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]| 1 | results, path = [], [] |
| 2 | def backtrack(start): |
| 3 | if len(path) == k: |
| 4 | results.append(list(path)) |
| 5 | return |
| 6 | need = k - len(path) |
| 7 | for i in range(start, n - need + 2): |
| 8 | path.append(i) |
| 9 | backtrack(i + 1) |
| 10 | path.pop() |
| 11 | backtrack(1) |
| 12 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Subsets record a group at every node of the decision tree, so you get every size from empty to full. Combinations ask for groups of one fixed size k. The loop and the i + 1 are exactly the same as in Subsets; the only change is when you record: only once len(path) == k, and then you stop going deeper.
🏀 The Analogy: Picking a Team of k Players
Think of n players with jersey numbers 1 to n, and you must list every possible team of k. To avoid writing the same team twice, always list a team's jerseys from smallest to largest. So after you pick jersey 3, you only look at jerseys 4 and up. The team [1, 3] gets written once; [3, 1] never appears, because nobody ever looks backward. As soon as a team has k players, write it down and step back to try the next player.
🔑 The Key Idea in the Code
backtrack(i + 1) does two jobs at once: it keeps i from being used twice in the same group, and it makes every group appear in increasing order only, so no group is ever listed twice.
✂️ The Loop Bound: Stop When There Aren't Enough Numbers Left
If the group still needs need = k - len(path) numbers, starting at a number too close to n can never fill it. The largest useful start is n - need + 1, so the loop is for i in range(start, n - need + 2). The answer is the same as looping up to n; the dead-end branches are simply never entered. Cut the bound one lower and every group that ends in n is lost.
Recording before the group is full: Recording at every node (the Subsets habit) returns groups of every size. Record only when
len(path) == k, andreturnright after, because a full group can't grow.Looping from 0 instead of
start: Starting each loop at the first number builds[1, 2]and[2, 1]as two different groups. Always loop fromstartand recurse withi + 1.Appending the live
path:results.append(path)stores a reference to the one shared list, which is empty when the search ends. Appendlist(path).Off-by-one in the pruning bound: The optional early stop allows
iup ton - (k - len(path)) + 1inclusive, so the range end isn - (k - len(path)) + 2. One less skips valid groups.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Return all combinations of k numbers" + "order does not matter" + small n (n <= 20) + a fixed group size k.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: path is always an increasing list of numbers from 1..n, and every number after path[-1] is still available. Complete when len(path) == k: record a copy and return, since a full group can't grow.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Recursing with
start + 1instead ofi + 1-- the next level then restarts too early, so a number can repeat ([2, 2]) and the same group appears in two orders ([2, 3]and[3, 2]).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Combinations. I build each group in increasing order with backtrack(start): the loop tries every number i from start upward, appends it to path, recurses, then pops it. A group of numbers has exactly one increasing order, so building only in that order produces each group once and never both [1, 2] and [2, 1]. When path has k numbers I save a copy and return. I also stop the loop early when too few numbers are left to fill the group, which removes dead branches without changing the answer. The trap is the recursive call: it must be backtrack(i + 1), not backtrack(start + 1), because the next pick has to come after the number I just picked; with start + 1 and n = 4, k = 2, I get [3, 2] next to [2, 3]. There are C(n, k) groups and each copy costs k, so it's O(k times C(n, k)) time and
O(k)extra space for path and the recursion."
Complexity & Mathematical Proof
O(k · C(n, k))
Look at the execution steps: the search records exactly C(n, k) groups, and copying each one with list(path) costs k. The internal nodes of the tree are prefixes of those groups, so the total work is O(k · C(n, k)).
O(k) Call Stack
The recursion never goes deeper than k levels, and path holds at most k numbers. The output itself holds C(n, k) groups of k numbers each.
Derivation Progression
Leaves = C(n, k)
Every recorded group is one leaf of the tree, and each group is produced exactly once.
Max Depth = k
A group is recorded (and the branch stops) as soon as it has k numbers.
k per recorded group
list(path) copies k numbers each time a group is recorded.
Variable Definitions
Largest number available (choose from 1..n)
Size of each group
Memory Architecture & Bounds
O(k) Call stack depth
O(k) Current group (path)
O(k · C(n, k)) Result groups
Boundary Best / Worst Cases
when or .
.
, largest when .
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "all possible combinations of k numbers from [1, n]", "order does not matter". Canonical combinations pattern: keep the candidate index strictly increasing so no group is built twice.
. Output size is , at most groups; the output, not the search, sets the cost.
At scale memory fails first: groups of numbers each. When the caller only iterates (for example, feeding each group to a job), stream the groups with a generator and yield a copy of path.