Problem Description

You are given a set of distinct positive integers nums. Your task is to find the largest subset where any two elements in the subset are divisible by each other.

Specifically, for any pair of elements (answer[i], answer[j]) in your subset, one of these conditions must be true:

• answer[i] % answer[j] == 0 (answer[i] is divisible by answer[j]), or
• answer[j] % answer[i] == 0 (answer[j] is divisible by answer[i])

The goal is to return the subset with the maximum number of elements that satisfies this divisibility property. If multiple valid subsets of the same maximum size exist, you can return any one of them.

For example, if nums = [1, 2, 4, 8], the entire array forms a valid subset because:

• 2 is divisible by 1
• 4 is divisible by 2 and 1
• 8 is divisible by 4, 2, and 1

The solution uses dynamic programming with the following approach:

1. Sort the array first to ensure smaller numbers come before larger ones
2. Use f[i] to track the length of the largest divisible subset ending at index i
3. For each element at position i, check all previous elements j where j < i
4. If nums[i] % nums[j] == 0, then nums[i] can extend the subset ending at j
5. Track the index k where the longest subset ends
6. Reconstruct the actual subset by backtracking from position k

The time complexity is O(n²) where n is the length of the input array, due to the nested loops checking divisibility relationships.

Intuition

The key insight is recognizing that if we have a valid divisible subset, and we sort it, the elements form a chain where each element divides the next one. For instance, [1, 2, 4, 8] forms a chain where 1|2, 2|4, and 4|8 (using | to denote "divides").

This observation leads us to think about the problem differently. If we sort the entire input array first, then for any valid subset, its elements will maintain a divisibility chain property when taken in sorted order.

Why is this helpful? Because it transforms our problem into finding the longest chain where each element divides the next. This is similar to finding the Longest Increasing Subsequence (LIS), but instead of comparing if nums[i] > nums[j], we check if nums[i] % nums[j] == 0.

The dynamic programming approach emerges naturally from this insight:

• For each position i, we ask: "What's the longest divisible chain that ends at this element?"
• To answer this, we look at all previous positions j < i
• If nums[i] is divisible by nums[j], then nums[i] can extend whatever chain ended at j
• We take the maximum among all such possibilities

The beauty of sorting first is that it guarantees we only need to check if the larger number is divisible by the smaller one (not both directions), simplifying our logic. Additionally, when we build a chain like [2, 4, 8], we know that 8 is divisible by 2 (not just by 4) due to the transitive property of divisibility - if 8 % 4 == 0 and 4 % 2 == 0, then 8 % 2 == 0.

This reduction to a chain-finding problem with dynamic programming gives us an efficient O(n²) solution.

Solution Approach

The implementation follows a dynamic programming approach with backtracking to reconstruct the solution:

Step 1: Sort the array

nums.sort()

Sorting ensures that for any valid divisible subset, elements appear in increasing order, simplifying our divisibility checks.

Step 2: Initialize DP array

f = [1] * n

Create array f where f[i] represents the length of the longest divisible subset ending at index i. Initialize all values to 1 since each element forms a valid subset by itself.

Step 3: Build DP table

for i in range(n):
    for j in range(i):
        if nums[i] % nums[j] == 0:
            f[i] = max(f[i], f[j] + 1)

For each position i, check all previous positions j. If nums[i] is divisible by nums[j], then nums[i] can extend the subset ending at j. Update f[i] to be the maximum of its current value or f[j] + 1.

Step 4: Track the best ending position

if f[k] < f[i]:
    k = i

Variable k keeps track of the index where the longest divisible subset ends. This helps us know where to start our backtracking.

Step 5: Reconstruct the subset

m = f[k]
i = k
ans = []
while m:
    if nums[k] % nums[i] == 0 and f[i] == m:
        ans.append(nums[i])
        k, m = i, m - 1
    i -= 1

Starting from position k with subset length m, work backwards:

• Check if nums[k] % nums[i] == 0 (ensuring divisibility)
• Check if f[i] == m (ensuring this element belongs to our optimal chain)
• If both conditions are met, add nums[i] to our answer
• Update k to i (new reference point) and decrement m (looking for the next element in the chain)
• Continue moving backwards with i -= 1

The reconstruction works because we're essentially tracing back the decisions made during the DP construction, picking elements that form the longest valid chain ending at position k.

Example Walkthrough

Let's walk through the solution with nums = [1, 2, 3, 4, 8].

Step 1: Sort the array Array is already sorted: [1, 2, 3, 4, 8]

Step 2: Initialize DP array f = [1, 1, 1, 1, 1] (each element forms a subset by itself)

Step 3: Build DP table

For i = 0 (nums[0] = 1): No previous elements, so f[0] = 1

For i = 1 (nums[1] = 2):

• Check j = 0: 2 % 1 == 0 ✓, so f[1] = max(1, f[0] + 1) = 2
• Result: f = [1, 2, 1, 1, 1]

For i = 2 (nums[2] = 3):

• Check j = 0: 3 % 1 == 0 ✓, so f[2] = max(1, f[0] + 1) = 2
• Check j = 1: 3 % 2 == 1 ✗, no update
• Result: f = [1, 2, 2, 1, 1]

For i = 3 (nums[3] = 4):

• Check j = 0: 4 % 1 == 0 ✓, so f[3] = max(1, f[0] + 1) = 2
• Check j = 1: 4 % 2 == 0 ✓, so f[3] = max(2, f[1] + 1) = 3
• Check j = 2: 4 % 3 == 1 ✗, no update
• Result: f = [1, 2, 2, 3, 1]

For i = 4 (nums[4] = 8):

• Check j = 0: 8 % 1 == 0 ✓, so f[4] = max(1, f[0] + 1) = 2
• Check j = 1: 8 % 2 == 0 ✓, so f[4] = max(2, f[1] + 1) = 3
• Check j = 2: 8 % 3 == 2 ✗, no update
• Check j = 3: 8 % 4 == 0 ✓, so f[4] = max(3, f[3] + 1) = 4
• Result: f = [1, 2, 2, 3, 4]

Step 4: Find best ending position Maximum value in f is 4 at index k = 4

Step 5: Reconstruct the subset Starting with k = 4, m = 4:

• i = 4: 8 % 8 == 0 ✓ and f[4] == 4 ✓ → Add 8, update k = 4, m = 3
• i = 3: 8 % 4 == 0 ✓ and f[3] == 3 ✓ → Add 4, update k = 3, m = 2
• i = 2: 4 % 3 == 1 ✗ → Skip
• i = 1: 4 % 2 == 0 ✓ and f[1] == 2 ✓ → Add 2, update k = 1, m = 1
• i = 0: 2 % 1 == 0 ✓ and f[0] == 1 ✓ → Add 1, update k = 0, m = 0

Final answer: [8, 4, 2, 1] (or reversed to [1, 2, 4, 8])

This forms a valid divisible subset where each pair satisfies the divisibility condition.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm consists of several parts:

• Sorting the array takes O(n log n) time
• The nested loops for building the DP array f:
  • Outer loop runs n times
  • Inner loop runs up to i times for each iteration
  • Total iterations: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²)
• The reconstruction phase (while loop):
  • In the worst case, iterates through all elements once, taking O(n) time

Overall time complexity is dominated by the nested loops: O(n log n) + O(n²) + O(n) = O(n²)

Space Complexity: O(n)

The space usage includes:

• Array f of size n to store the length of longest divisible subset ending at each index: O(n)
• The output array ans which can contain at most n elements: O(n)
• A few auxiliary variables (k, m, i): O(1)

Total space complexity: O(n) + O(n) + O(1) = O(n)

Note: If we don't count the output array as extra space (as is common in complexity analysis), the space complexity would just be O(n) for the DP array.

Common Pitfalls

Pitfall 1: Incorrect Divisibility Check Direction

Problem: A common mistake is checking nums[j] % nums[i] == 0 instead of nums[i] % nums[j] == 0 when building the DP array. Since the array is sorted in ascending order, we want to check if the larger number (nums[i]) is divisible by the smaller number (nums[j]).

Wrong approach:

if nums[j] % nums[i] == 0:  # Incorrect!
    dp[i] = max(dp[i], dp[j] + 1)

Correct approach:

if nums[i] % nums[j] == 0:  # Correct
    dp[i] = max(dp[i], dp[j] + 1)

Pitfall 2: Forgetting to Sort the Array

Problem: Without sorting, the DP approach breaks down because we rely on the transitive property of divisibility. If the array isn't sorted, we might miss valid subset extensions.

Example of failure without sorting:

nums = [4, 1, 2, 8]  # Unsorted
# Without sorting, when processing 2, we haven't seen 1 yet
# This leads to incorrect subset construction

Solution: Always sort the array first:

nums.sort()  # Essential step

Pitfall 3: Incorrect Reconstruction Logic

Problem: During backtracking, forgetting to check both conditions (nums[current_index] % nums[i] == 0 AND dp[i] == max_length) can lead to including wrong elements in the subset.

Wrong reconstruction:

while max_length > 0:
    if dp[i] == max_length:  # Missing divisibility check!
        result.append(nums[i])
        max_length -= 1
    i -= 1

Correct reconstruction:

while max_length > 0:
    if nums[current_index] % nums[i] == 0 and dp[i] == max_length:
        result.append(nums[i])
        current_index = i  # Update reference point
        max_length -= 1
    i -= 1

Pitfall 4: Not Updating the Reference Point During Reconstruction

Problem: Forgetting to update current_index when adding an element to the result causes incorrect divisibility checks in subsequent iterations.

Wrong approach:

if nums[current_index] % nums[i] == 0 and dp[i] == max_length:
    result.append(nums[i])
    # Forgot to update current_index!
    max_length -= 1

Correct approach:

if nums[current_index] % nums[i] == 0 and dp[i] == max_length:
    result.append(nums[i])
    current_index = i  # Must update to maintain chain integrity
    max_length -= 1

Pitfall 5: Edge Case with Single Element

Problem: Not handling the case where the input array has only one element, though the provided solution handles this correctly by initializing dp = [1] * n.

Prevention: Ensure the solution works for:

• Empty array (though typically problem constraints guarantee at least one element)
• Single element array: [3] should return [3]
• Arrays where no elements are divisible: [2, 3, 5] should return any single element