368.-largest-divisible-subset.md

368. Largest Divisible Subset

• Medium

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

Analysis

The problem may seem complicated at first galance, but after you think about it, when we try to add a num into the current list, we only need to compare it with the largest of the ones that are currently in the list.

class Solution:
    def largestDivisibleSubset(self, nums):
        if len(nums) == 0: return []
        nums.sort()
        sol = [[num] for num in nums]
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] % nums[j] == 0 and len(sol[i]) < len(sol[j]) + 1:
                    sol[i] = sol[j] + [nums[i]]
        return max(sol, key=len)