368. Largest Divisible Subset - Explanation

Problem Link

Description

Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

  • answer[i] % answer[j] == 0, or
  • answer[j] % answer[i] == 0

If there are multiple solutions, return any of them.

Example 1:

Input: nums = [1,2,3]

Output: [1,2]

Explanation: [1,3] is also accepted.

Example 2:

Input: nums = [1,2,4,8]

Output: [1,2,4,8]

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 2,000,000,000
  • All the integers in nums are unique.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Dynamic Programming (Top-Down)

Intuition

A divisible subset has a special property: if we sort the numbers, then for any pair in the subset, the larger number must be divisible by the smaller one. This means if we sort the array and pick elements in order, we only need to check divisibility with the most recently picked element. We can use recursion with memoization to try including or skipping each number.

Algorithm

  1. Sort the array in ascending order.
  2. Define a recursive function dfs(i, prevIndex) that returns the largest divisible subset starting from index i, where prevIndex is the index of the last included element (or -1 if none).
  3. At each index:
    • Option 1: Skip the current number.
    • Option 2: If no previous element exists or the current number is divisible by the previous one, include it and recurse.
  4. Memoize results based on (i, prevIndex) to avoid recomputation.
  5. Return the larger of the two options.
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        cache = {}  # (i, prevIndex) -> List

        def dfs(i, prevIndex):
            if i == len(nums):
                return []
            if (i, prevIndex) in cache:
                return cache[(i, prevIndex)]

            res = dfs(i + 1, prevIndex)  # Skip nums[i]
            if prevIndex == -1 or nums[i] % nums[prevIndex] == 0:
                tmp = [nums[i]] + dfs(i + 1, i)  # Include nums[i]
                res = tmp if len(tmp) > len(res) else res

            cache[(i, prevIndex)] = res
            return res

        return dfs(0, -1)

Time & Space Complexity

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

2. Dynamic Programming (Top-Down) Space Optimized

Intuition

We can simplify the state by observing that we only need to track the starting index, not the previous index. For each starting position, we find the longest divisible subset that begins there. When building the subset from index i, we look at all later indices j where nums[j] is divisible by nums[i] and take the best result.

Algorithm

  1. Sort the array in ascending order.
  2. Define dfs(i) that returns the largest divisible subset starting at index i.
  3. At each index i:
    • Initialize the result with just nums[i].
    • For each later index j where nums[j] % nums[i] == 0, recursively get the subset starting at j.
    • Prepend nums[i] to the best result and keep the longest.
  4. Memoize results for each starting index.
  5. Try all starting positions and return the longest subset found.
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        cache = {}

        def dfs(i):
            if i in cache:
                return cache[i]

            res = [nums[i]]
            for j in range(i + 1, len(nums)):
                if nums[j] % nums[i] == 0:
                    tmp = [nums[i]] + dfs(j)
                    if len(tmp) > len(res):
                        res = tmp

            cache[i] = res
            return res

        res = []
        for i in range(len(nums)):
            tmp = dfs(i)
            if len(tmp) > len(res):
                res = tmp
        return res

Time & Space Complexity

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

3. Dynamic Programming (Bottom-Up)

Intuition

We can convert the top-down approach to bottom-up. Processing from right to left, for each index we compute the longest divisible subset starting from that position. At each step, we check all later indices for valid extensions and build upon the precomputed results.

Algorithm

  1. Sort the array in ascending order.
  2. Create a DP array where dp[i] stores the longest divisible subset starting at index i.
  3. Initialize each dp[i] with just the element at that index.
  4. Iterate from right to left:
    • For each later index j, if nums[j] % nums[i] == 0, check if prepending nums[i] to dp[j] gives a longer subset.
    • Update dp[i] with the longest result.
    • Track the overall longest subset found.
  5. Return the longest subset.
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        dp = [[num] for num in nums]  # dp[i] = longest start at i
        res = []
        for i in range(len(nums) - 1, -1, -1):
            for j in range(i + 1, len(nums)):
                if nums[j] % nums[i] == 0:
                    tmp = [nums[i]] + dp[j]
                    dp[i] = tmp if len(tmp) > len(dp[i]) else dp[i]
            res = dp[i] if len(dp[i]) > len(res) else res
        return res

Time & Space Complexity

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

4. Dynamic Programming (Top-Down) + Tracing

Intuition

Instead of storing entire subsets in the DP table (which uses extra memory), we can store just two values per index: the length of the longest subset starting there, and the next index in that subset. After computing all lengths, we trace through the indices to reconstruct the actual subset.

Algorithm

  1. Sort the array in ascending order.
  2. Create a DP array where dp[i] = [maxLen, nextIndex].
  3. Define dfs(i) that returns the length of the longest subset starting at index i:
    • For each later index j where nums[j] % nums[i] == 0, compute the length via dfs(j) + 1.
    • Track which j gave the best length for tracing.
  4. Find the starting index with the maximum length.
  5. Reconstruct the subset by following the nextIndex pointers.
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]

        def dfs(i):
            if dp[i][0] != -1:
                return dp[i][0]

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

            return dp[i][0]

        max_len, start_index = 1, 0
        for i in range(n):
            if dfs(i) > max_len:
                max_len = dfs(i)
                start_index = i

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

        return subset

Time & Space Complexity

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

5. Dynamic Programming (Bottom-Up) + Tracing

Intuition

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.

Algorithm

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

Time & Space Complexity

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

Common Pitfalls

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.