Largest Divisible Subset

How it works

This is the iterative version of the tracing approach. We process indices from left to right, looking backward for valid predecessors. For each position, we store the length of the longest subset ending there and a pointer to the previous index. This is similar to the classic Longest Increasing Subsequence pattern.

Steps

1. Sort the array in ascending order.
2. Create a DP array where dp[i] = [maxLen, prevIndex], initialized with length 1 and no predecessor.
3. For each index i, check all earlier indices j:
   • If nums[i] % nums[j] == 0 and extending from j gives a longer subset, update dp[i].
   • Track the index with the overall maximum length.
4. Reconstruct the subset by following the prevIndex pointers backward from the best ending index.

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(n)

Things to watch for

Forgetting to Sort the Array First

The divisibility property only guarantees transitivity when elements are sorted. If a divides b and b divides c, then a divides c, but this chain only works reliably when processing elements in ascending order. Skipping the sort step means you might miss valid subset extensions or incorrectly reject valid ones.

Checking Divisibility in the Wrong Direction

After sorting in ascending order, when comparing nums[i] and nums[j] where i < j, you must check if nums[j] % nums[i] == 0 (larger divisible by smaller). A common mistake is checking nums[i] % nums[j] == 0, which will always be false for distinct positive integers when nums[i] < nums[j].

Only Returning the Length Instead of the Actual Subset

The problem asks for the subset itself, not just its size. When using DP with length tracking only, you must also maintain a way to reconstruct the path, typically through parent pointers or by storing the actual subsets. Forgetting this reconstruction step means you can compute the correct length but cannot output the required elements.

from typing import List

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        dp = [[1, -1] for _ in range(n)]  # dp[i] = [maxLen, prevIdx]

        max_len, start_index = 1, 0

        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[j][0] + 1 > dp[i][0]:
                    dp[i][0] = dp[j][0] + 1
                    dp[i][1] = j

            if dp[i][0] > max_len:
                max_len = dp[i][0]
                start_index = i

        subset = []
        while start_index != -1:
            subset.append(nums[start_index])
            start_index = dp[start_index][1]
        return subset

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(2, -1)); // dp[i] = {maxLen, prevIdx}

        int maxLen = 1, startIndex = 0;
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
            dp[i][1] = -1;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[j][0] + 1 > dp[i][0]) {
                    dp[i][0] = dp[j][0] + 1;
                    dp[i][1] = j;
                }
            }

            if (dp[i][0] > maxLen) {
                maxLen = dp[i][0];
                startIndex = i;
            }
        }

        vector<int> subset;
        while (startIndex != -1) {
            subset.push_back(nums[startIndex]);
            startIndex = dp[startIndex][1];
        }
        return subset;
    }
};