368. Largest Divisible Subset

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

Solution

---

Python3

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        N = len(nums)
        nums.sort()
        dp = [1] * N
        parent = [-1] * N
        maxSubsetSize = 1
 
        for i in range(N):
            for j in range(i + 1, N):
                if nums[j] % nums[i] == 0:
                    if dp[i] + 1 > dp[j]:
                        dp[j] = dp[i] + 1
                        parent[j] = i
                        maxSubsetSize = max(maxSubsetSize, dp[j])
        
        index = dp.index(maxSubsetSize)
        res = [nums[index]]
        while parent[index] != -1:
            res.append(nums[parent[index]])
            index = parent[index]
 
        return res