Hi👋SpeedAlgo • Deliberate Practice & Cognitive Ergonomics for Software Engineers

An interactive algorithm mastery and technical interview preparation platform published by Hi👋WebEnterprise. Built for senior and staff software engineers preparing for rigorous coding screens at top tech companies (FAANG/MAMAA).

12 Core Algorithmic Patterns & 143 Practice Problems

  • 1. Two Pointers (5 Paradigms, 25 Problems): Converging pointers, sorted pair sums, container with most water, trapping rain water, 3Sum, plus the Sliding Window and Fast & Slow Pointers paradigms (Floyd cycle detection, monotonic window invariants, longest substrings, minimum window).
  • 2. Binary Search (7 Paradigms, 10 Problems): Monotonic predicate partitioning, boundary searching, rotated arrays, median of two sorted arrays, matrix median on value range.
  • 3. Bit Manipulation (4 Paradigms, 7 Problems): Bitmasking, XOR tricks, counting set bits, subset enumeration via bitmasks.
  • 4. Math & Geometry (4 Paradigms, 9 Problems): Sieve of Eratosthenes, integer/roman conversions, modular arithmetic, geometric simulation.
  • 5. Tree/Graph Depth-First Search (6 Paradigms, 15 Problems): Path sums, lowest common ancestor, tree diameter, subtree serialization, validating BSTs.
  • 6. Tree/Graph Breadth-First Search (4 Paradigms, 11 Problems): Level-order traversals, shortest path, rotting oranges, word ladders.
  • 7. Graphs (5 Paradigms, 13 Problems): Topological sort, cycle detection, Dijkstra, bipartite validation, network delay.
  • 8. Backtracking (5 Paradigms, 13 Problems): Subsets, permutations, combinations, constraint satisfaction, pruning, N-Queens.
  • 9. Dynamic Programming (6 Paradigms, 13 Problems): Memoization vs tabulation, knapsack, coin change, edit distance, longest common subsequence.
  • 10. Heap / Priority Queue (6 Paradigms, 8 Problems): Running medians, top-k elements, interval scheduling, IPO, k-way merges.
  • 11. Advanced Data Structures (3 Paradigms, 10 Problems): Trie, Union-Find, LRU Cache, LFU Cache, Monotonic Stacks.
  • 12. Intervals & Stack / Miscellaneous (2 Paradigms, 9 Problems): Merge intervals, daily temperatures, largest rectangle in histogram, trapping rain water via stack.

4-Stage Deliberate Practice Framework

  1. Stage 1 (Compare & Learn): Multi-language Rosetta Stone contrasting abstract invariants with concrete solutions across Python, C#, Java, TypeScript, C++, Go, and Rust.
  2. Stage 2 (Active Recall): Reconstruct algorithmic template invariants from memory with real-time feedback before looking at solutions.
  3. Stage 3 (Senior SWE AI Mock Coach): Simulated senior mock interview evaluating Big-O space/time tradeoffs, edge cases, and code reviews in Monaco Editor.
  4. Stage 4 (Solve on Your Own): Timed sandbox challenges verified against automated test suites in Python, C#, Java, and TypeScript.

Equipped with SM-2 Spaced Repetition Review Hub, Studio Cockpit workspace layout, and interactive study notes.

Pricing, Access & Commercial Terms

  • Core Curriculum: 100% Free. No credit card required.
  • Compute Coins: 40 free coins upon signup, +20 daily login bonus, +25 referral bonus.
  • 24-Hour AI Coaching Pass: 5 compute coins unlocks unlimited senior SWE AI coaching for a full 24 hours.
  • BYOK (Bring Your Own Key): Completely free unlimited AI coaching if using your own Gemini/OpenAI API key.
  • Refund & Subscription Policy: No recurring charges, no subscription traps, and no paid paywalls. Free tier provides full learning path.
  • Platform Operator: Hi👋WebEnterprise Inc. Support & policies at hispeedalgo.com.
Skip to main content
Hi👋SpeedAlgo

Invariant-First Algorithmic Mastery

155Items
Theory Context•Backtracking & State Search
MediumLC 77

Combinations — Choose k of n (LeetCode 77)

You will see that choosing k of n is the Subsets loop with one change: record only when the group has exactly k numbers.

Target Frequency:AmazonGoogleMeta

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

Example 1
Input:n = 4, k = 2
Output:[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 6 ways to choose 2 of the 4 numbers. [2,1] is not listed separately because it is the same group as [1,2].
Example 2
Input:n = 1, k = 1
Output:[[1]]
Explanation: With a single number, the only group of size 1 is [1].

⚖️Formal Constraints & Bounds

  • 1 <= n <= 20

  • 1 <= k <= n

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

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

🧩Subproblem 1: Forward-Only Number Choice

At each level, try only numbers from start to n. Anything below start was already passed over, which keeps every group in increasing order.

Mathematical Recurrence / Code Invariant
for i in range(start, n + 1):

Step-by-Step Execution Trace Table

Code / Blueprint
                        [ ] (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
  1. Step 1 (Root, start=1): path = [], size 0 < 2. Try numbers 1 to 4.
  2. Step 2 (Choose 1): path = [1], recurse with start = 2.
  3. Step 3 (Choose 2): path = [1, 2]. Size is 2 →\rightarrow→ Record [1, 2] ✅ and return.
  4. Step 4 (Pop 2, choose 3): path = [1, 3] →\rightarrow→ Record [1, 3] ✅.
  5. Step 5 (Pop 3, choose 4): path = [1, 4] →\rightarrow→ Record [1, 4] ✅. The loop at [1] ends.
  6. Step 6 (Pop 1, choose 2 at the root): path = [2], recurse with start = 3. Record [2, 3] ✅ and [2, 4] ✅.
  7. Step 7 (Choose 3 at the root): path = [3], recurse with start = 4. Record [3, 4] ✅.
  8. Step 8 (Choose 4 at the root): path = [4], recurse with start = 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 (42)=6\binom{4}{2} = 6(24​)=6 groups.
Full Walkthrough8 Steps
Input:n = 4, k = 2Expected:[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
1🌱 ROOT(Root, start=1)
path = []
path = [], size 0 < 2. Try numbers 1 to 4.
2🟢 CHOOSE(Choose 1)
path = [1]
path = [1], recurse with start = 2.
3✅ RECORD / GOAL(Choose 2)
path = [1, 2]
path = [1, 2]. Size is 2 →\rightarrow→ Record [1, 2] ✅ and return.
4⚡ FIFO DRAIN(Pop 2, choose 3)
path = [1, 3]
path = [1, 3] →\rightarrow→ Record [1, 3] ✅.
5⚡ FIFO DRAIN(Pop 3, choose 4)
path = [1, 4]
path = [1, 4] →\rightarrow→ Record [1, 4] ✅. The loop at [1] ends.
6🌱 ROOT(Pop 1, choose 2 at the root)
path = [2]
path = [2], recurse with start = 3. Record [2, 3] ✅ and [2, 4] ✅.
7🌱 ROOT(Choose 3 at the root)
path = [3]
path = [3], recurse with start = 4. Record [3, 4] ✅.
8🌱 ROOT(Choose 4 at the root)
path = [4]
path = [4], recurse with start = 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 (42)=6\binom{4}{2} = 6(24​)=6 groups.
Core Invariant Specification & Code Shape
Archetype Code Shape
Python
1results, path = [], []
2def backtrack(start):
3 if len(path) == k: results.append(list(path)); return
4 for i in range(start, n + 1):
5 path.append(i); backtrack(i + 1); path.pop()
6backtrack(1); return results

Target: Combinations — Choose k of n (LeetCode 77). The group is full: record a copy and stop going deeper

Boundary Model: State Space Tree: Choose -> Explore -> Un-choose

Branch exploration via in-place mutation followed by immediate backtrack restoration. Sibling deduplication prunes duplicate subtrees.

Loop Invariant Termination

Recursive base case: if len(path) == target: record copy; for i in range(start, n): choose, recurse, un-choose.

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.

🪄 Breaking Down the Code's "Magic Trick"
Code / Blueprint
if len(path) == k:              # the group is full
    results.append(list(path))  # record a COPY
    return                      # a full group can't grow: stop here
for i in range(start, n + 1):   # only numbers AFTER the last pick
    path.append(i)
    backtrack(i + 1)            # i + 1: each number used at most once
    path.pop()
 

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.

✂️ Optional Speed-Up: Stop When There Aren't Enough Numbers Left

If the group still needs k - len(path) numbers, starting at a number too close to n can never fill it. The largest useful start is n - (k - len(path)) + 1, so the loop can be for i in range(start, n - (k - len(path)) + 2). The answer is the same; the dead-end branches are simply never entered.

💡 Summary

Subsets, combinations and permutations share one loop. Subsets record at every node, combinations record only at size k, and permutations drop start and loop from 0 with a used array. Combinations of size k from n numbers number exactly (nk)\binom{n}{k}(kn​).

🧠 Variable Roles & Pattern Refresher:

  • start: One-Way Door: the smallest number still allowed, so groups are built in increasing order only.
  • path: The group being built; it never has more than k numbers.
  • len(path) == k: Record point: save list(path) and return.
  • backtrack(i + 1): Move strictly forward; each number is used at most once.

  • Recording before the group is full: Recording at every node (the Subsets habit) returns groups of every size. Record only when len(path) == k, and return right 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 from start and recurse with i + 1.

  • Appending the live path: results.append(path) stores a reference to the one shared list, which is empty when the search ends. Append list(path).

  • Off-by-one in the pruning bound: The optional early stop allows i up to n - (k - len(path)) + 1 inclusive, so the range end is n - (k - len(path)) + 2. One less skips valid groups.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer recognizes 'choose k of n' and reuses the Subsets loop with a single change to the record step.

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

  • Recording at every node like Subsets -- that returns groups of every size, not just size k.

  • Recursing with start + 1 instead of i + 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]).

  • Appending path instead of list(path) -- every saved group ends up as the same (empty) list.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"I build groups in increasing order with backtrack(start): if len(path) == k I record a copy and return; otherwise I loop i from start to n, append i, recurse with i + 1, then pop. Increasing order guarantees each group appears once. There are C(n, k) groups and copying each costs k, so the time is O(k · C(n, k)) and the extra space is O(k) for the path and the recursion."

So: spot 'every group of size k, order doesn't matter', loop from start with i + 1, record only at size k, and pitch O(k · C(n, k)).

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

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)).

SPACE COMPLEXITY

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.

Formal Recurrence Relation

T(n,k)=O(k⋅(nk))T(n, k) = O(k \cdot \binom{n}{k})T(n,k)=O(k⋅(kn​))

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)).

Derivation Progression

Leaf Count

Leaves = C(n, k)

Every recorded group is one leaf of the tree, and each group is produced exactly once.

Tree Depth Bound

Max Depth = k

A group is recorded (and the branch stops) as soon as it has k numbers.

Copy Cost

k per recorded group

list(path) copies k numbers each time a group is recorded.

Variable Definitions

nnn

Largest number available (choose from 1..n)

kkk

Size of each group

Memory Architecture & Bounds

🟣 Call Stack

O(k) Call stack depth

🔵 Auxiliary Heap

O(k) Current group (path)

🟢 Output Space

O(k · C(n, k)) Result groups

Boundary Best / Worst Cases

Best Case

O(n)O(n)O(n) when k=1k = 1k=1 or k=nk = nk=n.

Average Case

O(k⋅(nk))O(k \cdot \binom{n}{k})O(k⋅(kn​)).

Worst Case

O(k⋅(nk))O(k \cdot \binom{n}{k})O(k⋅(kn​)), largest when k≈n/2k \approx n/2k≈n/2.

Decision & State-Space Search Tree

Decision & State-Space Search Tree
Synthesizing vector architecture diagram...
Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

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.

CONSTRAINTS & BOUNDS

n≤20,k≤nn \le 20, k \le nn≤20,k≤n. Output size is (nk)\binom{n}{k}(kn​), at most (2010)=184756\binom{20}{10} = 184756(1020​)=184756. Optional pruning: stop the loop once too few numbers remain to fill kkk slots, i≤n−(k−len(path))+1i \le n - (k - len(path)) + 1i≤n−(k−len(path))+1.

FAANG PRODUCTION TRAPS & EDGE CASES

Recording at every node (Subsets habit) returns every size; pruning bound off-by-one: the range end is n−(k−len(path))+2n - (k - len(path)) + 2n−(k−len(path))+2.

Core Algorithmic State Invariants

1. Forward-Only Increasing Order Invariant

State is the start number: every number from start to n is still available, and every number below it is permanently passed over. Recursing with backtrack(i + 1) keeps each group in increasing order, so a group is built once and no number repeats inside it.

2. Fixed-Size Record Point

The only difference from Subsets is where results are recorded: when len(path) == k, results.append(list(path)) saves a copy and the call returns, because a full group can't grow. Shorter paths are never recorded.

3. Exact Count and Bounded Depth

The search records exactly C(n, k) groups and never goes deeper than k levels, giving O(k · C(n, k)) time and O(k) extra space. Optionally, stopping the loop at n - (k - len(path)) + 1 skips branches that can't reach size k.

Theory Context•Backtracking & State Search
MediumLC 77

Combinations — Choose k of n (LeetCode 77)

You will see that choosing k of n is the Subsets loop with one change: record only when the group has exactly k numbers.

Target Frequency:AmazonGoogleMeta

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

Example 1
Input:n = 4, k = 2
Output:[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 6 ways to choose 2 of the 4 numbers. [2,1] is not listed separately because it is the same group as [1,2].
Example 2
Input:n = 1, k = 1
Output:[[1]]
Explanation: With a single number, the only group of size 1 is [1].

⚖️Formal Constraints & Bounds

  • 1 <= n <= 20

  • 1 <= k <= n

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

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

🧩Subproblem 1: Forward-Only Number Choice

At each level, try only numbers from start to n. Anything below start was already passed over, which keeps every group in increasing order.

Mathematical Recurrence / Code Invariant
for i in range(start, n + 1):

Step-by-Step Execution Trace Table

Code / Blueprint
                        [ ] (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
  1. Step 1 (Root, start=1): path = [], size 0 < 2. Try numbers 1 to 4.
  2. Step 2 (Choose 1): path = [1], recurse with start = 2.
  3. Step 3 (Choose 2): path = [1, 2]. Size is 2 →\rightarrow→ Record [1, 2] ✅ and return.
  4. Step 4 (Pop 2, choose 3): path = [1, 3] →\rightarrow→ Record [1, 3] ✅.
  5. Step 5 (Pop 3, choose 4): path = [1, 4] →\rightarrow→ Record [1, 4] ✅. The loop at [1] ends.
  6. Step 6 (Pop 1, choose 2 at the root): path = [2], recurse with start = 3. Record [2, 3] ✅ and [2, 4] ✅.
  7. Step 7 (Choose 3 at the root): path = [3], recurse with start = 4. Record [3, 4] ✅.
  8. Step 8 (Choose 4 at the root): path = [4], recurse with start = 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 (42)=6\binom{4}{2} = 6(24​)=6 groups.
Full Walkthrough8 Steps
Input:n = 4, k = 2Expected:[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
1🌱 ROOT(Root, start=1)
path = []
path = [], size 0 < 2. Try numbers 1 to 4.
2🟢 CHOOSE(Choose 1)
path = [1]
path = [1], recurse with start = 2.
3✅ RECORD / GOAL(Choose 2)
path = [1, 2]
path = [1, 2]. Size is 2 →\rightarrow→ Record [1, 2] ✅ and return.
4⚡ FIFO DRAIN(Pop 2, choose 3)
path = [1, 3]
path = [1, 3] →\rightarrow→ Record [1, 3] ✅.
5⚡ FIFO DRAIN(Pop 3, choose 4)
path = [1, 4]
path = [1, 4] →\rightarrow→ Record [1, 4] ✅. The loop at [1] ends.
6🌱 ROOT(Pop 1, choose 2 at the root)
path = [2]
path = [2], recurse with start = 3. Record [2, 3] ✅ and [2, 4] ✅.
7🌱 ROOT(Choose 3 at the root)
path = [3]
path = [3], recurse with start = 4. Record [3, 4] ✅.
8🌱 ROOT(Choose 4 at the root)
path = [4]
path = [4], recurse with start = 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 (42)=6\binom{4}{2} = 6(24​)=6 groups.
Core Invariant Specification & Code Shape
Archetype Code Shape
Python
1results, path = [], []
2def backtrack(start):
3 if len(path) == k: results.append(list(path)); return
4 for i in range(start, n + 1):
5 path.append(i); backtrack(i + 1); path.pop()
6backtrack(1); return results

Target: Combinations — Choose k of n (LeetCode 77). The group is full: record a copy and stop going deeper

Boundary Model: State Space Tree: Choose -> Explore -> Un-choose

Branch exploration via in-place mutation followed by immediate backtrack restoration. Sibling deduplication prunes duplicate subtrees.

Loop Invariant Termination

Recursive base case: if len(path) == target: record copy; for i in range(start, n): choose, recurse, un-choose.

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.

🪄 Breaking Down the Code's "Magic Trick"
Code / Blueprint
if len(path) == k:              # the group is full
    results.append(list(path))  # record a COPY
    return                      # a full group can't grow: stop here
for i in range(start, n + 1):   # only numbers AFTER the last pick
    path.append(i)
    backtrack(i + 1)            # i + 1: each number used at most once
    path.pop()
 

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.

✂️ Optional Speed-Up: Stop When There Aren't Enough Numbers Left

If the group still needs k - len(path) numbers, starting at a number too close to n can never fill it. The largest useful start is n - (k - len(path)) + 1, so the loop can be for i in range(start, n - (k - len(path)) + 2). The answer is the same; the dead-end branches are simply never entered.

💡 Summary

Subsets, combinations and permutations share one loop. Subsets record at every node, combinations record only at size k, and permutations drop start and loop from 0 with a used array. Combinations of size k from n numbers number exactly (nk)\binom{n}{k}(kn​).

🧠 Variable Roles & Pattern Refresher:

  • start: One-Way Door: the smallest number still allowed, so groups are built in increasing order only.
  • path: The group being built; it never has more than k numbers.
  • len(path) == k: Record point: save list(path) and return.
  • backtrack(i + 1): Move strictly forward; each number is used at most once.

  • Recording before the group is full: Recording at every node (the Subsets habit) returns groups of every size. Record only when len(path) == k, and return right 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 from start and recurse with i + 1.

  • Appending the live path: results.append(path) stores a reference to the one shared list, which is empty when the search ends. Append list(path).

  • Off-by-one in the pruning bound: The optional early stop allows i up to n - (k - len(path)) + 1 inclusive, so the range end is n - (k - len(path)) + 2. One less skips valid groups.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer recognizes 'choose k of n' and reuses the Subsets loop with a single change to the record step.

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

  • Recording at every node like Subsets -- that returns groups of every size, not just size k.

  • Recursing with start + 1 instead of i + 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]).

  • Appending path instead of list(path) -- every saved group ends up as the same (empty) list.

The 60-Second Interview Pitch

Say this out loud before you type a single line

"I build groups in increasing order with backtrack(start): if len(path) == k I record a copy and return; otherwise I loop i from start to n, append i, recurse with i + 1, then pop. Increasing order guarantees each group appears once. There are C(n, k) groups and copying each costs k, so the time is O(k · C(n, k)) and the extra space is O(k) for the path and the recursion."

So: spot 'every group of size k, order doesn't matter', loop from start with i + 1, record only at size k, and pitch O(k · C(n, k)).

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

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)).

SPACE COMPLEXITY

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.

Formal Recurrence Relation

T(n,k)=O(k⋅(nk))T(n, k) = O(k \cdot \binom{n}{k})T(n,k)=O(k⋅(kn​))

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)).

Derivation Progression

Leaf Count

Leaves = C(n, k)

Every recorded group is one leaf of the tree, and each group is produced exactly once.

Tree Depth Bound

Max Depth = k

A group is recorded (and the branch stops) as soon as it has k numbers.

Copy Cost

k per recorded group

list(path) copies k numbers each time a group is recorded.

Variable Definitions

nnn

Largest number available (choose from 1..n)

kkk

Size of each group

Memory Architecture & Bounds

🟣 Call Stack

O(k) Call stack depth

🔵 Auxiliary Heap

O(k) Current group (path)

🟢 Output Space

O(k · C(n, k)) Result groups

Boundary Best / Worst Cases

Best Case

O(n)O(n)O(n) when k=1k = 1k=1 or k=nk = nk=n.

Average Case

O(k⋅(nk))O(k \cdot \binom{n}{k})O(k⋅(kn​)).

Worst Case

O(k⋅(nk))O(k \cdot \binom{n}{k})O(k⋅(kn​)), largest when k≈n/2k \approx n/2k≈n/2.

Decision & State-Space Search Tree

Decision & State-Space Search Tree
Synthesizing vector architecture diagram...
Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

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.

CONSTRAINTS & BOUNDS

n≤20,k≤nn \le 20, k \le nn≤20,k≤n. Output size is (nk)\binom{n}{k}(kn​), at most (2010)=184756\binom{20}{10} = 184756(1020​)=184756. Optional pruning: stop the loop once too few numbers remain to fill kkk slots, i≤n−(k−len(path))+1i \le n - (k - len(path)) + 1i≤n−(k−len(path))+1.

FAANG PRODUCTION TRAPS & EDGE CASES

Recording at every node (Subsets habit) returns every size; pruning bound off-by-one: the range end is n−(k−len(path))+2n - (k - len(path)) + 2n−(k−len(path))+2.

Core Algorithmic State Invariants

1. Forward-Only Increasing Order Invariant

State is the start number: every number from start to n is still available, and every number below it is permanently passed over. Recursing with backtrack(i + 1) keeps each group in increasing order, so a group is built once and no number repeats inside it.

2. Fixed-Size Record Point

The only difference from Subsets is where results are recorded: when len(path) == k, results.append(list(path)) saves a copy and the call returns, because a full group can't grow. Shorter paths are never recorded.

3. Exact Count and Bounded Depth

The search records exactly C(n, k) groups and never goes deeper than k levels, giving O(k · C(n, k)) time and O(k) extra space. Optionally, stopping the loop at n - (k - len(path)) + 1 skips branches that can't reach size k.

Rosetta Dual-Monaco Comparison
Python 3
CANONICAL INVARIANT TEMPLATE
Loading...
CONCRETE: COMBINATIONS — CHOOSE K OF N (LEETCODE 77)
T = O(k · C(n, k))S = O(k) Call Stack
Loading...
Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale
Canonical InvariantConcrete CodeEngineering Rationale
if is_complete(path, state):if len(path) == k:The group is full: record a copy and stop going deeper
for option in get_options(state):for i in range(start, n + 1):Only numbers after the last one picked are options
apply_choice(path, state, option)path.append(i)Add number i to the group
backtrack(path, state, results, ...)backtrack(i + 1)Continue from i + 1, so i can't be picked again and no group is built in two orders
undo_choice(path, state, option)path.pop()Remove i so the next loop iteration starts from the same group
© 2026 Hi👋WebEnterprise. All rights reserved.
Sitemap•llms.txt•