The question

Largest Divisible Subset

Given a list of distinct positive integers, return the largest subset in which every pair divides evenly in one direction: for any two values, the larger is divisible by the smaller. The output can be in ascending order. If several largest subsets exist, return any one.

Input: [1, 2, 3, 8, 4]One answer: [1, 2, 4, 8]Length: 4

Turn divisibility into a chain

Bottom-up DP is natural here: solve the best chain ending at each number, then connect it to an earlier chain.

1

Sort ascending

Only compare a later, larger value with an earlier, smaller one. The useful test is larger % smaller == 0.

2

Grow the best ending

dp[i] is the longest chain ending at nums[i]. Every value starts at length 1; a valid earlier chain may extend it.

3

Remember the path

parent[i] stores the prior index chosen for the best chain. Follow those links backward, then reverse the answer.

Why one divisibility check is enough: if 8 is divisible by 4 and 4 by 2, then 8 is also divisible by 2. Transitivity makes every pair in the chain compatible.

Interactive walkthrough

Watch the chain take shape

Compare candidates, update dp and parent, then trace the answer.

O(n²) time · O(n) extra space
Current ending i Candidate j Best chain Reconstructing

Sorted values · dp length · parent index

parent − means start of chain

Current step

Ready to sort the input.

Best chain so far

Length 0

ResultFollow the steps to reveal the subset
—
Step 0 / 0

What happens at each pair?

For the current ending i, look at every earlier j. Extend its chain only if the numbers divide evenly and it improves the length.

nums[i] % nums[j] == 0
and dp[j] + 1 > dp[i]

A tie keeps the first chain found. That is fine because the problem accepts any maximum subset.

Why initialize with ones?

Each number is a valid subset by itself, so every dp[i] starts at 1. A parent of -1 says that number starts its chain.

The largest dp[i] identifies an endpoint. Following parents visits the chain from largest to smallest, so reverse it before returning.

Python reference

Bottom-up DP with parent links

This is the same transition and reconstruction used by the walkthrough. The empty input returns an empty subset.

from typing import List

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        nums = sorted(nums)
        n = len(nums)
        dp = [1] * n
        parent = [-1] * n
        best_len = 1
        best_end = 0

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

            if dp[i] > best_len:
                best_len = dp[i]
                best_end = i

        answer = []
        current = best_end
        while current != -1:
            answer.append(nums[current])
            current = parent[current]

        answer.reverse()
        return answer