Largest Divisible Subset

▶

Steps

setup

Initialize and Sort Input

The input list [1, 2, 3] is sorted in ascending order to facilitate divisibility checks and early breaks.

💡 Sorting ensures that if a number is not divisible by a smaller number, no larger number after it will be divisible either, enabling early breaks.

Line:

nums.sort()

💡 Sorting is a crucial preprocessing step that enables efficient pruning in later steps.

setup

Initialize dp and prev arrays

Arrays dp and prev are initialized. dp[i] = 1 means each number alone forms a subset of length 1. prev[i] = -1 means no previous index linked yet.

💡 dp tracks the length of the largest divisible subset ending at each index; prev helps reconstruct the subset later.

Line:

dp = [1] * n
prev = [-1] * n
max_index = 0

💡 Initialization sets the base case: each element is a subset of size 1 by itself.

fill_row

Start outer loop with i=0

Begin iterating over nums with i=0, representing the first element 1. No inner loop runs since j < 0 is invalid.

💡 The first element forms a subset of length 1 by itself; no previous elements to check.

Line:

for i in range(n):
    for j in range(i - 1, -1, -1):

💡 At i=0, dp[0] remains 1 and prev[0] remains -1.

fill_row

Start outer loop with i=1

Move to i=1, representing number 2. Begin inner loop with j=0 to check divisibility with nums[0]=1.

💡 We try to extend the subset ending at j=0 by including nums[1] if divisible.

Line:

for i in range(n):
    for j in range(i - 1, -1, -1):

💡 We are exploring if 2 can extend the subset ending at 1.

compare

Check divisibility: nums[1] % nums[0] == 0

Check if 2 % 1 == 0, which is true. Since dp[0] + 1 = 2 > dp[1] = 1, update dp[1] to 2 and prev[1] to 0.

💡 This means the subset ending at index 0 can be extended by nums[1] to form a longer divisible subset.

Line:

if nums[i] % nums[j] == 0:
    if dp[j] + 1 > dp[i]:
        dp[i] = dp[j] + 1
        prev[i] = j

💡 We see how dp and prev arrays track the longest divisible subset ending at each index.

fill_row

Update max_index after i=1

Since dp[1] = 2 > dp[max_index] = dp[0] = 1, update max_index to 1.

💡 max_index tracks the index where the largest divisible subset ends.

Line:

if dp[i] > dp[max_index]:
    max_index = i

💡 Tracking max_index allows efficient reconstruction of the largest subset later.

fill_row

Start outer loop with i=2

Move to i=2, representing number 3. Begin inner loop with j=1 to check divisibility with nums[1]=2.

💡 We check if 3 can extend the subset ending at 2, then check j=0 if needed.

Line:

for i in range(n):
    for j in range(i - 1, -1, -1):

💡 We explore possible extensions of subsets ending before index 2.

compare

Check divisibility: nums[2] % nums[1] == 0

Check if 3 % 2 == 0, which is false. Early break from inner loop since nums is sorted and no smaller j will divide 3.

💡 Early break avoids unnecessary checks, improving efficiency.

Line:

if nums[i] % nums[j] == 0:
    ...
else:
    break

💡 Sorting allows pruning inner loop when divisibility fails, saving computation.

compare

Check divisibility: nums[2] % nums[0] == 0

Since inner loop broke early, no further checks for j=0 are done. dp[2] and prev[2] remain unchanged.

💡 Early break prevents checking j=0, demonstrating pruning effectiveness.

Line:

break

💡 Early break skips unnecessary divisibility checks for smaller indices.

fill_row

Update max_index after i=2

dp[2] = 1 is not greater than dp[max_index] = dp[1] = 2, so max_index remains 1.

💡 max_index tracks the largest subset found so far and does not change here.

Line:

if dp[i] > dp[max_index]:
    max_index = i

💡 max_index correctly points to the end of the largest divisible subset.

reconstruct

Start reconstructing the largest divisible subset

Initialize an empty result list and start from max_index=1 to reconstruct the subset backwards using prev array.

💡 Reconstruction follows the chain of indices stored in prev to build the subset.

Line:

result = []
while max_index >= 0:

💡 Reconstruction is essential to retrieve the actual subset, not just its length.

reconstruct

Append nums[max_index] = 2 to result

Append nums[1] = 2 to result. Update max_index to prev[1] = 0 to continue reconstruction.

💡 We add the current element and move to its predecessor in the subset chain.

Line:

result.append(nums[max_index])
max_index = prev[max_index]

💡 Following prev links reconstructs the subset in reverse order.

reconstruct

Append nums[max_index] = 1 to result

Append nums[0] = 1 to result. Update max_index to prev[0] = -1, ending reconstruction loop.

💡 We have reached the start of the subset chain.

Line:

result.append(nums[max_index])
max_index = prev[max_index]

💡 Reconstruction complete when max_index becomes -1.

reconstruct

Reverse result to get final subset

Reverse the result list [2, 1] to get [1, 2], the largest divisible subset in correct order.

💡 Reversing is necessary because reconstruction collected elements backwards.

Line:

return result[::-1]

💡 The final answer is the largest divisible subset found by the algorithm.

from typing import List

def largestDivisibleSubset(nums: List[int]) -> List[int]:
    if not nums:
        return []  # STEP 1: Handle empty input
    nums.sort()  # STEP 1: Sort input
    n = len(nums)
    dp = [1] * n  # STEP 2: Initialize dp array
    prev = [-1] * n  # STEP 2: Initialize prev array
    max_index = 0  # STEP 2: Track index of largest subset

    for i in range(n):  # STEP 3: Outer loop over nums
        for j in range(i - 1, -1, -1):  # STEP 4: Inner loop backwards
            if nums[i] % nums[j] == 0:  # STEP 5: Check divisibility
                if dp[j] + 1 > dp[i]:  # STEP 5: Update dp and prev if longer
                    dp[i] = dp[j] + 1
                    prev[i] = j
            else:
                break  # STEP 8: Early break if not divisible
        if dp[i] > dp[max_index]:  # STEP 6 & 10: Update max_index
            max_index = i

    result = []  # STEP 11: Prepare to reconstruct subset
    while max_index >= 0:  # STEP 12 & 13: Reconstruct subset
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]  # STEP 14: Reverse and return

📊

Largest Divisible Subset - Watch the Algorithm Execute, Step by Step

Watching each comparison and update helps you understand how the algorithm efficiently finds the largest divisible subset by building on smaller solutions and pruning unnecessary checks.

enteringnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

enteringnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

choosingnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

Remaining

i=0

choosingnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

Tried

i=0

Remaining

i=1

choosingnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

Tried

j=0

choosingnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

Tried

i=1

Remaining

i=2

choosingnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

Tried

i=0i=1

Remaining

i=2

pruningnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

Tried

j=1

✂ 3 % 2 != 0, early break

backtrackingnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

Tried

j=1

✂ early break prevents j=0 check

choosingnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

Tried

i=0i=1i=2

choosingnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

choosingnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

Partial: [2]

backtrackingnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

Partial: [2, 1]

backtrackingnums=[1,2,3]

Call Path (current → root)

largestDivisibleSubset([1, 2, 3])

Found 1: [1,2]

Key Takeaways

✓ Sorting the input array enables early breaks in the inner loop, significantly reducing unnecessary divisibility checks.

This optimization is subtle and not obvious from code alone; watching the early break in action clarifies its importance.

✓ The dp array stores the length of the largest divisible subset ending at each index, while the prev array stores the predecessor index to reconstruct the subset.

Seeing dp and prev update step-by-step helps understand how dynamic programming builds solutions incrementally.

✓ Reconstruction of the subset by following prev pointers from max_index back to -1 reveals the actual subset, not just its size.

This backtracking step is often overlooked but critical to retrieving the final answer.

Practice

1. You are given a set of distinct positive integers and a target sum. You need to find all unique combinations where the chosen numbers sum to the target. Each number can be chosen multiple times. Which algorithmic approach best guarantees finding all valid combinations efficiently without missing any or producing duplicates?

easy

A. Greedy algorithm that picks the largest candidate repeatedly until the sum is reached or exceeded.

B. Backtracking with sorting and frequency counting to avoid duplicates and prune early when sum exceeds target.

C. Dynamic programming using a 2D table to count the number of combinations without generating them explicitly.

D. Pure brute force recursion that tries all subsets without pruning or sorting.

Solution

1. Step 1: Understand problem constraints

   The problem requires all unique combinations summing to target, allowing reuse of candidates.

2. Step 2: Evaluate algorithm suitability

   Greedy fails because it can miss combinations; pure brute force is correct but inefficient; DP counts combinations but doesn't generate them; backtracking with sorting and frequency counting avoids duplicates and prunes search space efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning and frequency counting is the standard approach [OK]

Hint: Backtracking with pruning avoids duplicates and excessive search [OK]

Common Mistakes:

• Assuming greedy always works for sum problems
• Confusing counting with generating combinations

2. Consider the following code snippet for counting max bitwise-OR subsets. What is the returned value when input is [1, 2, 3]?

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_or = 0
        count = 0
        for mask in range(1, 1 << n):
            current_or = 0
            for i in range(n):
                if mask & (1 << i):
                    current_or |= nums[i]
            if current_or > max_or:
                max_or = current_or
                count = 1
            elif current_or == max_or:
                count += 1
        return count

sol = Solution()
print(sol.countMaxOrSubsets([1, 2, 3]))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Enumerate all non-empty subsets and their OR

   Subsets: {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} with ORs 1, 2, 3, 3, 3, 3, 3 respectively.

2. Step 2: Identify max OR and count subsets with that OR

   Max OR is 3; subsets with OR=3 are {3}, {1,2}, {1,3}, {2,3}, {1,2,3} -> 5 subsets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counted 5 subsets with max OR 3 -> matches 5 [OK]

Hint: Count subsets with OR equal to max OR -> 5 [OK]

Common Mistakes:

• Counting empty subset as valid
• Miscounting subsets with max OR

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

4. Examine the following buggy code snippet for partitioning an array into k equal sum subsets using backtracking with bitmask memoization. Which line contains the subtle bug that can cause incorrect results or inefficiency?

medium

A. Line 2: missing check if total is divisible by k

B. Line 6: sorting nums in descending order

C. Line 14: memoizing result after recursive call

D. Line 18: checking if element is unused and fits in current subset

Solution

1. Step 1: Identify missing early pruning

   Line 2 calculates total but does not check if total % k != 0, which is critical to avoid futile search.

2. Step 2: Verify other lines

   Sorting descending (line 6) is correct for pruning; memoization (line 14) and usage check (line 18) are correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without divisibility check, algorithm wastes time exploring impossible partitions [OK]

Hint: Always check divisibility before backtracking [OK]

Common Mistakes:

• Forgetting early divisibility check
• Misplacing memoization

5. What is the time complexity of the optimal iterative approach for generating all unique subsets from an array of length n that may contain duplicates?

medium

A. O(n^2) because of nested loops over the array

B. O(2^n) since each element doubles the subsets

C. O(2^n * n) due to generating all subsets and copying them

D. O(n * 2^n) because sorting dominates the complexity

Solution

1. Step 1: Identify main operations affecting complexity

   Sorting takes O(n log n), which is dominated by subset generation. The algorithm generates all subsets (2^n) and copies subsets of average length O(n).

2. Step 2: Calculate total time complexity

   Generating all subsets is O(2^n), and copying each subset of length up to n leads to O(2^n * n) total time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Copying subsets causes the extra factor n, not just 2^n [OK]

Hint: Copying subsets adds factor n to 2^n subsets [OK]

Common Mistakes:

• Ignoring subset copying cost and saying O(2^n)
• Confusing sorting cost as dominant
• Mistaking nested loops as O(n^2)