Combinations (Choose K from N)

▶

Steps

setup

Initialize the first combination

The algorithm starts by creating the initial combination [1, 2] for k=2.

💡 This initialization sets the starting point for generating all combinations in lexicographic order.

Line:

comb = list(range(1, k + 1))

💡 The first combination is always the smallest lexicographic sequence of length k.

fill_row

Add initial combination to results

The current combination [1, 2] is copied and added to the results list.

💡 Adding the current combination before attempting to generate the next ensures no valid combination is missed.

Line:

result.append(comb[:])

💡 Every valid combination must be recorded before moving forward.

compare

Find rightmost element to increment: start at index 1

The algorithm sets i to the last index (1) to find an element that can be incremented.

💡 Starting from the right ensures the next combination is lexicographically next smallest.

Line:

i = k - 1

💡 We try to increment the last element first to get the next combination.

compare

Check if comb[1] == max allowed value

Check if comb[1] (2) equals n - k + i + 1 = 4 - 2 + 1 + 1 = 4, which it does not.

💡 If the element is at its max, we must move left to find an incrementable element.

Line:

while i >= 0 and comb[i] == n - k + i + 1:
    i -= 1

💡 Since comb[1] can be incremented, we will increment it next.

insert

Increment comb[1]

Increment comb[1] from 2 to 3 to get the next combination candidate.

💡 Incrementing the rightmost incrementable element moves to the next lexicographic combination.

Line:

comb[i] += 1

💡 Incrementing here generates the next valid combination starting point.

fill_cells

Reset elements to the right of i

Since i=1 is the last index, no elements to the right need resetting.

💡 Resetting ensures the combination remains strictly increasing and valid.

Line:

for j in range(i + 1, k):
    comb[j] = comb[j - 1] + 1

💡 No reset needed here, but this step is crucial when i is not the last index.

fill_row

Add new combination [1, 3] to results

The updated combination [1, 3] is copied and appended to the results list.

💡 Recording each valid combination ensures the final output is complete.

Line:

result.append(comb[:])

💡 The algorithm outputs combinations as soon as they are generated.

compare

Find rightmost element to increment: start at index 1

Set i=1 again to check if comb[1] (3) can be incremented further.

💡 We always try to increment the rightmost element first for lex order.

Line:

i = k - 1

💡 The search for increment position repeats until no increments are possible.

compare

Check if comb[1] == max allowed value

Check if comb[1] (3) equals 4, it does not, so i=1 is valid for increment.

💡 If the element is less than max, it can be incremented.

Line:

while i >= 0 and comb[i] == n - k + i + 1:
    i -= 1

💡 We found the rightmost element to increment again.

insert

Increment comb[1] to 4

Increment comb[1] from 3 to 4 to form the next combination candidate.

💡 Incrementing the last element moves to the next lexicographic combination.

Line:

comb[i] += 1

💡 The combination is now [1, 4], the next valid pair.

fill_cells

Reset elements to the right of i

No elements to the right of i=1, so no reset needed.

💡 Resetting maintains the strictly increasing order of combinations.

Line:

for j in range(i + 1, k):
    comb[j] = comb[j - 1] + 1

💡 No reset needed here, but this step is essential when i < k-1.

fill_row

Add new combination [1, 4] to results

Add the combination [1, 4] to the results list.

💡 Each valid combination is recorded immediately after generation.

Line:

result.append(comb[:])

💡 The results list grows with each new valid combination.

compare

Find rightmost element to increment: start at index 1

Set i=1 to check if comb[1] (4) can be incremented.

💡 We try to increment the last element first to find the next combination.

Line:

i = k - 1

💡 The search for increment position continues until no increments are possible.

compare

Check if comb[1] == max allowed value

comb[1] (4) equals max allowed value 4, so decrement i to 0.

💡 If the element is at max, move left to find incrementable element.

Line:

while i >= 0 and comb[i] == n - k + i + 1:
    i -= 1

💡 The algorithm moves left to find the next element to increment.

compare

Check if comb[0] == max allowed value

comb[0] (1) is less than max allowed 3, so i=0 is valid for increment.

💡 We found the leftmost element that can be incremented.

Line:

while i >= 0 and comb[i] == n - k + i + 1:
    i -= 1

💡 Incrementing comb[0] will generate new combinations starting with 2.

insert

Increment comb[0] from 1 to 2

Increment comb[0] to 2 to start generating combinations beginning with 2.

💡 Incrementing the left element resets the sequence to a new range.

Line:

comb[i] += 1

💡 The combination now starts with 2, and elements to the right will be reset.

fill_cells

Reset elements to the right of i=0

Reset comb[1] to comb[0] + 1 = 3, updating combination to [2, 3].

💡 Resetting ensures the combination remains strictly increasing after increment.

Line:

for j in range(i + 1, k):
    comb[j] = comb[j - 1] + 1

💡 The combination is now valid and ready to be added.

fill_row

Add new combination [2, 3] to results

Add the combination [2, 3] to the results list.

💡 Each new valid combination is recorded immediately.

Line:

result.append(comb[:])

💡 The results list now contains four combinations.

compare

Find rightmost element to increment: start at index 1

Set i=1 to check if comb[1] (3) can be incremented.

💡 Try to increment the last element first for next combination.

Line:

i = k - 1

💡 The search for increment position continues.

compare

Check if comb[1] == max allowed value

comb[1] (3) is less than max allowed 4, so i=1 is valid for increment.

💡 We found the rightmost element to increment again.

Line:

while i >= 0 and comb[i] == n - k + i + 1:
    i -= 1

💡 Incrementing comb[1] will generate the next combination.

insert

Increment comb[1] to 4

Increment comb[1] from 3 to 4 to form the next combination [2, 4].

💡 Incrementing the last element generates the next valid pair.

Line:

comb[i] += 1

💡 The combination is now [2, 4].

fill_cells

Reset elements to the right of i=1

No elements to the right of i=1, so no reset needed.

💡 Resetting maintains order but is not needed here.

Line:

for j in range(i + 1, k):
    comb[j] = comb[j - 1] + 1

💡 No reset needed for last element increment.

fill_row

Add new combination [2, 4] to results

Add the combination [2, 4] to the results list.

💡 Each valid combination is recorded immediately.

Line:

result.append(comb[:])

💡 The results list now contains five combinations.

compare

Find rightmost element to increment: start at index 1

Set i=1 to check if comb[1] (4) can be incremented.

💡 Try to increment the last element first for next combination.

Line:

i = k - 1

💡 The search for increment position continues.

compare

Check if comb[1] == max allowed value

comb[1] (4) equals max allowed 4, so decrement i to 0.

💡 If the element is at max, move left to find incrementable element.

Line:

while i >= 0 and comb[i] == n - k + i + 1:
    i -= 1

💡 The algorithm moves left to find the next element to increment.

compare

Check if comb[0] == max allowed value

comb[0] (2) is less than max allowed 3, so i=0 is valid for increment.

💡 We found the leftmost element that can be incremented.

Line:

while i >= 0 and comb[i] == n - k + i + 1:
    i -= 1

💡 Incrementing comb[0] will generate new combinations starting with 3.

insert

Increment comb[0] from 2 to 3

Increment comb[0] to 3 to start generating combinations beginning with 3.

💡 Incrementing the left element resets the sequence to a new range.

Line:

comb[i] += 1

💡 The combination now starts with 3, and elements to the right will be reset.

fill_cells

Reset elements to the right of i=0

Reset comb[1] to comb[0] + 1 = 4, updating combination to [3, 4].

💡 Resetting ensures the combination remains strictly increasing after increment.

Line:

for j in range(i + 1, k):
    comb[j] = comb[j - 1] + 1

💡 The combination is now valid and ready to be added.

fill_row

Add new combination [3, 4] to results

Add the combination [3, 4] to the results list.

💡 Each valid combination is recorded immediately.

Line:

result.append(comb[:])

💡 The results list now contains all six combinations.

compare

Attempt to find next increment position

Set i=1 to check if comb[1] (4) can be incremented, but it is max, so decrement i to 0; comb[0] (3) is also max, decrement i to -1.

💡 When no elements can be incremented, the algorithm terminates.

Line:

while i >= 0 and comb[i] == n - k + i + 1:
    i -= 1
if i < 0:
    break

💡 The algorithm has generated all combinations and stops.

from typing import List

def combine(n: int, k: int) -> List[List[int]]:
    result = []
    comb = list(range(1, k + 1))  # STEP 1: Initialize combination
    while True:
        result.append(comb[:])  # STEP 2,7,12,18,23,29: Add current combination
        i = k - 1  # STEP 3,8,13,19,24,29: Start from last index
        while i >= 0 and comb[i] == n - k + i + 1:  # STEP 4,9,14,15,25,26,30: Find incrementable element
            i -= 1
        if i < 0:  # STEP 30: No more increments, break
            break
        comb[i] += 1  # STEP 5,10,16,21,27: Increment element
        for j in range(i + 1, k):  # STEP 6,11,17,22,28: Reset elements to right
            comb[j] = comb[j - 1] + 1
    return result

if __name__ == '__main__':
    print(combine(4, 2))  # Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

📊

Combinations (Choose K from N) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step reveals how the algorithm efficiently finds the next valid combination without generating duplicates or missing any, which is hard to grasp from code alone.

enteringn=4k=2

Call Path (current → root)

combine(4,2)

Remaining

start with [1,2]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

[1,2] added to results

Partial: [1, 2]

Found 1: [1,2]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Remaining

check if comb[1] can be incremented

Partial: [1, 2]

Found 1: [1,2]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

comb[1] not max, i=1

Partial: [1, 2]

Found 1: [1,2]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

increment comb[1] to 3

Partial: [1, 3]

Found 1: [1,2]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

no reset needed

Partial: [1, 3]

Found 1: [1,2]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

[1,3] added to results

Partial: [1, 3]

Found 2: [1,2] [1,3]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Remaining

check if comb[1] can be incremented

Partial: [1, 3]

Found 2: [1,2] [1,3]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

comb[1] not max, i=1

Partial: [1, 3]

Found 2: [1,2] [1,3]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

increment comb[1] to 4

Partial: [1, 4]

Found 2: [1,2] [1,3]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

no reset needed

Partial: [1, 4]

Found 2: [1,2] [1,3]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

[1,4] added to results

Partial: [1, 4]

Found 3: [1,3] [1,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Remaining

check if comb[1] can be incremented

Partial: [1, 4]

Found 3: [1,3] [1,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

comb[1] max, i=0

Remaining

check if comb[0] can be incremented

Partial: [1, 4]

Found 3: [1,3] [1,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

comb[0] not max, i=0

Partial: [1, 4]

Found 3: [1,3] [1,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

increment comb[0] to 2

Partial: [2, 4]

Found 3: [1,3] [1,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

reset comb[1] to 3

Partial: [2, 3]

Found 3: [1,3] [1,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

[2,3] added to results

Partial: [2, 3]

Found 4: [1,4] [2,3]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Remaining

check if comb[1] can be incremented

Partial: [2, 3]

Found 4: [1,4] [2,3]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

comb[1] not max, i=1

Partial: [2, 3]

Found 4: [1,4] [2,3]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

increment comb[1] to 4

Partial: [2, 4]

Found 4: [1,4] [2,3]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

no reset needed

Partial: [2, 4]

Found 4: [1,4] [2,3]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

[2,4] added to results

Partial: [2, 4]

Found 5: [2,3] [2,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Remaining

check if comb[1] can be incremented

Partial: [2, 4]

Found 5: [2,3] [2,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

comb[1] max, i=0

Remaining

check if comb[0] can be incremented

Partial: [2, 4]

Found 5: [2,3] [2,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

comb[0] not max, i=0

Partial: [2, 4]

Found 5: [2,3] [2,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

increment comb[0] to 3

Partial: [3, 4]

Found 5: [2,3] [2,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

reset comb[1] to 4

Partial: [3, 4]

Found 5: [2,3] [2,4]

choosingn=4k=2

Call Path (current → root)

combine(4,2)

Tried

[3,4] added to results

Partial: [3, 4]

Found 6: [2,4] [3,4]

pruningn=4k=2

Call Path (current → root)

combine(4,2)

Tried

comb[1] max, i=0comb[0] max, i=-1

Partial: [3, 4]

✂ No element can be incremented further

Found 6: [2,4] [3,4]

Key Takeaways

✓ The algorithm generates combinations in lexicographic order by incrementing the rightmost possible element.

This insight is hard to see from code alone because the increment and reset logic is subtle and intertwined.

✓ Resetting elements to the right of the incremented position ensures combinations remain strictly increasing and valid.

Visualizing this reset clarifies why the algorithm never produces duplicates or invalid sequences.

✓ The stopping condition occurs when no element can be incremented further, signaling completion.

Seeing the decrement of i to -1 and the break condition helps understand how the algorithm knows when to stop.

Practice

1. Consider the following Python code implementing the optimal backtracking with bitmask and memoization approach for the Matchsticks to Square problem. Given the input [1,1,2,2,2], what is the final return value of makesquare([1,1,2,2,2])?

easy

A. True

B. Depends on the order of matchsticks

C. Raises an exception due to index error

D. False

Solution

1. Step 1: Calculate total and side length

   Total = 1+1+2+2+2 = 8, side = 8/4 = 2.

2. Step 2: Trace backtracking calls

   Sorted sticks: [2,2,2,1,1]. The algorithm tries to form sides of length 2. It can form three sides with three 2's, and the last side with two 1's. Hence, returns true.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum divisible by 4 and sticks fit sides exactly [OK]

Hint: Sum divisible by 4 and sticks fit sides exactly [OK]

Common Mistakes:

• Forgetting to sort and prune
• Assuming order affects result
• Miscounting sides formed

2. Consider the following Python function implementing backtracking with bitmask memoization for partitioning an array into k equal sum subsets. Given nums = [4, 3, 2, 3, 5, 2, 1] and k = 4, what is the final return value of canPartitionKSubsets(nums, k)?

easy

A. True

B. False

C. Raises an exception due to index error

D. Returns None

Solution

1. Step 1: Calculate total and target sum

   Total sum is 4+3+2+3+5+2+1=20, target per subset = 20/4=5.

2. Step 2: Trace backtracking with sorted nums

   Sorted nums: [5,4,3,3,2,2,1]. The algorithm finds subsets: {5}, {4,1}, {3,2}, {3,2} all summing to 5, so returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All subsets sum to target, so partition possible [OK]

Hint: Sum divisible by k and backtracking finds valid subsets [OK]

Common Mistakes:

• Miscounting sum or target
• Assuming no solution due to order

3. The following code attempts to count subsets with sum K using space-optimized DP. Identify the line that contains a subtle bug that can cause incorrect results.

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(num, K + 1):
            dp[j] += dp[j - num]
    return dp[K]

medium

A. for j in range(num, K + 1):

B. dp[0] = 1

C. dp = [0] * (K + 1)

D. dp[j] += dp[j - num]

Solution

1. Step 1: Analyze iteration order

   The inner loop iterates forward from num to K, which causes dp[j] to use updated dp values from the same iteration, leading to overcounting.

2. Step 2: Correct iteration direction

   To avoid overcounting, the inner loop must iterate backward from K down to num.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration in DP causes incorrect counts -> bug in loop range [OK]

Hint: Inner loop must iterate backward to avoid reuse of updated dp values [OK]

Common Mistakes:

• Using forward iteration in space-optimized DP
• Misunderstanding dp update dependencies

4. Suppose the problem is modified so that letters can be toggled multiple times, allowing reuse of characters in permutations (e.g., toggling the same letter case multiple times in different positions). Which modification to the backtracking approach correctly handles this variant without generating duplicates?

hard

A. Use a visited set to track permutations and skip duplicates after generation

B. Modify recursion to allow toggling letters multiple times but prune branches that revisit the same index

C. Change the algorithm to generate permutations with replacement by increasing recursion depth beyond string length

D. Use iterative BFS with a queue that enqueues toggled strings and avoids revisiting states

Solution

1. Step 1: Understand reuse variant

   Allowing reuse means letters can be toggled multiple times in different positions, increasing state space and possible duplicates.

2. Step 2: Identify correct approach

   Iterative BFS with a queue can track states and avoid revisiting duplicates efficiently, unlike naive recursion which may generate duplicates or infinite loops.

3. Step 3: Why other options fail

   Visited sets after generation are inefficient; pruning recursion by index doesn't prevent reuse; increasing recursion depth breaks problem constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   BFS with state tracking handles reuse and duplicates [OK]

Hint: Use BFS with visited states to handle reuse [OK]

Common Mistakes:

• Trying to prune recursion by index only
• Ignoring duplicates generated by reuse

5. Suppose the Matchsticks to Square problem is modified so that each matchstick can be used multiple times (unlimited reuse). Which of the following algorithmic changes correctly adapts the solution to this variant?

hard

A. Use backtracking without bitmask, allowing repeated selection of sticks, and prune when side length exceeded.

B. Keep the bitmask to track used sticks but allow multiple bits per stick to represent reuse counts.

C. Remove the bitmask and use a classic unbounded knapsack DP to check if four sides can be formed from unlimited sticks.

D. Sort sticks and greedily assign sticks to sides repeatedly until all sides are formed.

Solution

1. Step 1: Understand unlimited reuse impact

   Unlimited reuse means the problem becomes an unbounded partition problem, not a subset partition.

2. Step 2: Identify suitable algorithm

   Bitmask tracking used sticks is invalid since sticks can be reused infinitely. Backtracking without bitmask is inefficient. Greedy fails due to partition constraints. Unbounded knapsack DP correctly models unlimited usage.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Unbounded knapsack fits unlimited reuse scenario [OK]

Hint: Unbounded knapsack fits unlimited reuse scenario [OK]

Common Mistakes:

• Trying to track usage with bitmask for unlimited reuse
• Using greedy for partitioning
• Ignoring pruning in backtracking