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 solution for Combination Sum II. What is the final returned list when calling combinationSum2([1,2,2], 4)?

easy

A. [[1,2,2]]

B. [[1,2],[2]]

C. [[1,2],[2,2]]

D. [[1,2],[2,2],[1,2,2]]

Solution

1. Step 1: Sort candidates and start backtracking

   Sorted candidates: [1,2,2]. Start from index 0 with target=4.

2. Step 2: Explore combinations skipping duplicates at same level

   Try 1 -> target=3, then try 2 at next index -> target=1, next 2 is duplicate at same level skipped. No further candidates fit. Backtrack and try 2 at index 1 -> target=2, next 2 at index 2 -> target=0, add [2,2]. Both [1,2,2] and [2,2] are valid unique combinations.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both [1,2,2] and [2,2] sum to 4 without reuse and duplicates skipped [OK]

Hint: Duplicate skipping prevents repeated combinations [OK]

Common Mistakes:

• Including partial sums like [2]
• Allowing reuse of elements
• Not skipping duplicates at same recursion level

2. You need to generate all possible subsets of a given set of distinct integers. Which approach guarantees generating every subset exactly once with a time complexity proportional to the number of subsets times the size of each subset?

easy

A. Greedy algorithm that picks elements based on their value order

B. Enumerate all bitmasks from 0 to 2^n - 1, selecting elements where bits are set

C. Dynamic programming to count subsets without generating them

D. Sorting the array and using two pointers to find pairs

Solution

1. Step 1: Understand the problem

   We want to generate all subsets of a set, which are 2^n in number.

2. Step 2: Identify the approach that enumerates all subsets

   Bitmask enumeration from 0 to 2^n - 1 maps each bit to an element's inclusion, guaranteeing all subsets exactly once.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets systematically [OK]

Hint: Bitmask from 0 to 2^n-1 enumerates all subsets [OK]

Common Mistakes:

• Thinking greedy or sorting can generate all subsets efficiently

3. What is the worst-case time complexity of the optimized dynamic programming solution for the Largest Divisible Subset problem, where n is the number of elements in the input array?

medium

A. O(n^2) due to nested loops checking divisibility pairs

B. O(2^n) because all subsets are considered

C. O(n^3) because of triple nested loops for subset checks

D. O(n log n) due to sorting and linear DP

Solution

1. Step 1: Identify main operations

   Sorting takes O(n log n). The DP uses two nested loops: outer loop over n elements, inner loop up to i elements.

2. Step 2: Analyze nested loops

   Each pair (i,j) is checked once, resulting in O(n^2) divisibility checks. Early break may speed up in practice but worst case remains O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP nested loops dominate complexity [OK]

Hint: DP nested loops -> O(n^2) worst case [OK]

Common Mistakes:

• Confusing sorting time as dominant (O(n log n))
• Assuming triple nested loops due to subset checks
• Thinking brute force complexity applies to DP

4. The following code attempts to find the largest divisible subset but contains a subtle bug. Identify the line with the bug.

def largestDivisibleSubset(nums):
    if not nums:
        return []
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_index = 0

    for i in range(n):
        for j in range(i - 1, -1, -1):
            if nums[j] % nums[i] == 0:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            else:
                break
        if dp[i] > dp[max_index]:
            max_index = i

    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]

medium

A. Line with 'result.append(nums[max_index])'

B. Line with 'dp = [1] * n'

C. Line with 'max_index = 0'

D. Line with 'if nums[j] % nums[i] == 0:'

Solution

1. Step 1: Check divisibility condition

   The condition should be nums[i] % nums[j] == 0 because we want to check if current number is divisible by a smaller number.

2. Step 2: Understand impact of bug

   Using nums[j] % nums[i] == 0 reverses the divisibility logic, causing incorrect dp updates and wrong subsets.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct divisibility check is crucial for correctness [OK]

Hint: Divisibility check direction matters [OK]

Common Mistakes:

• Swapping divisor and dividend in modulo check
• Not sorting input before DP
• Incorrect subset reconstruction

5. What is the time complexity of the optimal backtracking solution for letter case permutation on a string of length n with k letters (non-digit characters)?

medium

A. O(2^k * n) because only letters toggle case and each permutation requires joining n characters

B. O(2^k * k) because only letters are toggled and digits are skipped

C. O(n * 2^n) because each character doubles the permutations

D. O(n^2) because of nested recursion and string concatenation

Solution

1. Step 1: Identify branching factor

   Only letters (k of them) cause branching, each with 2 choices, so total permutations are 2^k.

2. Step 2: Calculate work per permutation

   Each permutation requires joining n characters to form a string, so O(n) per permutation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Time is exponential in letters, linear in string length [OK]

Hint: Complexity depends on letters, not total length [OK]

Common Mistakes:

• Assuming all characters double permutations
• Ignoring join cost per permutation