Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

After sorting, a divisible subset can be viewed as a chain: each smaller number divides the next larger one. Divisibility is transitive, so extending such a chain with a number that divides its smallest element preserves compatibility with every element. This allows dynamic programming over the chain's smallest member.

Approach

Sort nums and initialize dp[i] to the singleton subset containing nums[i].
Process indices from right to left so the best chain for every larger starting value is already known.
For each j > i with nums[j] % nums[i] == 0, consider extending dp[j] by appending nums[i]. Python constructs this copied candidate before testing its length; JavaScript copies only if the candidate will be longer than the current subset. Retain only a strictly longer chain.
Track the longest subset across all starting indices and return it. The stored arrays list their chains in descending order, which is allowed because only subset membership matters. Equal-length alternatives need not replace the existing answer.

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()

        dp = [[x] for x in nums]
        res = []

        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                if nums[j] % nums[i] == 0:
                    curr = dp[j] + [nums[i]]
                    dp[i] = curr if len(curr) > len(dp[i]) else dp[i]
            res = dp[i] if len(dp[i]) > len(res) else res
        
        return res

Complexity analysis

Let n = nums.length and L be the longest divisible chain. Sorting costs O(n log n), and the nested DP examines O(n^2) pairs. Python copies a subset for every divisible pair, even when it does not improve the result; JavaScript checks for improvement before copying. Each copy costs at most O(L), giving a common safe bound of O(n log n + n^2 L) time and O(nL) auxiliary space for stored subsets and temporary copies, which also covers linear sorting workspace. Using L <= n gives the coarse bounds O(n^3) time and O(n^2) space. Under the actual constraints, distinct positive values in a divisible chain at least double, so nums[i] <= 2 * 10^9 limits L to 31; this tightens the bounds to O(n^2) time and O(n) auxiliary space.