Skip to content

368. Largest Divisible Subset

Difficulty Topics

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 * 109
  • All the integers in nums are unique.

Solution

largest-divisible-subset.py
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        dp = [1] * n
        parents = [-1] * n
        mmax = 1

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

        maxi = dp.index(mmax)
        res = [nums[maxi]]
        while parents[maxi] != -1:
            maxi = parents[maxi]
            res.append(nums[maxi])

        return res