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. Consider the following Python function that counts subsets with sum K using a space-optimized DP approach. What is the output when called with arr = [1, 2, 3, 3] and K = 6?

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

print(count_subsets_space_optimized(arr, K))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0,0] since dp[0]=1 and K=6.

2. Step 2: Process each number updating dp

   After processing 1: dp = [1,1,0,0,0,0,0] After 2: dp = [1,1,1,1,0,0,0] After first 3: dp = [1,1,1,2,1,1,1] After second 3: dp = [1,1,1,3,2,2,3]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[6] = 5 subsets sum to 6 [OK]

Hint: Trace dp updates backward to avoid double counting [OK]

Common Mistakes:

• Forgetting to iterate backward in dp array
• Off-by-one errors in dp indices

2. You need to generate all possible subsets of a given set of distinct integers. Which algorithmic approach guarantees enumerating every subset exactly once, including the empty subset, without missing or duplicating any subset?

easy

A. Greedy algorithm that picks elements based on a heuristic to maximize subset size

B. Dynamic programming approach that builds subsets by summing elements to target values

C. Backtracking with include/exclude decisions at each element to explore all subset combinations

D. Sorting the array and then using two pointers to find pairs that form subsets

Solution

1. Step 1: Understand problem requirements

   The problem requires enumerating all subsets, which means exploring all combinations of including or excluding each element.

2. Step 2: Identify suitable algorithm

   Backtracking with include/exclude decisions systematically explores all subsets without duplication or omission, including the empty subset.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backtracking ensures all subsets are generated [OK]

Hint: Include/exclude backtracking covers all subsets [OK]

Common Mistakes:

• Confusing subset generation with greedy or DP sum problems

3. What is the time complexity of generating all subsets of an array of size n using bitmask enumeration, and why is the common misconception that it is O(2^n) incorrect?

medium

A. O(n^2) because we iterate over n elements twice

B. O(2^n) because there are 2^n subsets

C. O(n * 2^n) because each subset can have up to n elements and we build each subset by checking n bits

D. O(n) because we process each element once

Solution

1. Step 1: Count subsets and subset size

   There are 2^n subsets, and each subset can have up to n elements.

2. Step 2: Analyze bitmask enumeration cost

   For each of the 2^n masks, we check n bits to build the subset, resulting in O(n * 2^n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time depends on both number of subsets and subset size [OK]

Hint: Each subset requires O(n) to build, total O(n*2^n) [OK]

Common Mistakes:

• Ignoring subset size in complexity
• Assuming O(2^n) only
• Confusing with DP complexities

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

5. Suppose the problem changes: now each element in the input array can be chosen multiple times (unlimited reuse), and duplicates still exist. Which modification to the iterative approach correctly generates all unique subsets with duplicates and unlimited reuse?

hard

A. Keep the same code but remove the duplicate skipping condition to allow reuse.

B. Sort the array, and for each element, always start from index 0 when adding new subsets to allow reuse, but skip duplicates at the same recursion level.

C. Sort the array, and for each element, start from the previous start index for duplicates, but allow reuse by appending to all existing subsets including newly added ones in the same iteration.

D. Use backtracking with a visited array to track reuse and skip duplicates by sorting.

Solution

1. Step 1: Understand unlimited reuse impact

   Unlimited reuse means subsets can include the same element multiple times, so the iteration must consider all existing subsets each time.

2. Step 2: Modify iteration start index

   To allow reuse, always start from index 0 when adding new subsets, so elements can be appended multiple times. However, duplicates must still be skipped at the same recursion level to avoid repeated subsets.

3. Step 3: Confirm skipping duplicates at recursion level

   Skipping duplicates at the same recursion level prevents generating identical subsets multiple times despite reuse.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Starting from 0 allows reuse; skipping duplicates avoids repeats [OK]

Hint: Start from 0 to allow reuse; skip duplicates at recursion level [OK]

Common Mistakes:

• Removing duplicate skipping causes duplicates
• Starting from previous start index blocks reuse
• Using visited array unnecessarily complicates iterative approach