368. Largest Divisible Subset

Problem Statement

link: LeetCode.cn LeetCode

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:

Input: nums = [1,2,3] Output: [1,2]

Input: nums = [1,2,4,8] Output: [1,2,4,8]

Solution Approach

The solution employs dynamic programming to find the largest divisible subset in the given array nums.

Algorithm

1. Sorting: Sort the input array nums in ascending order to ensure divisibility properties.

2. Dynamic Programming: Initialize a dynamic programming array dp, where dp[i] represents the largest divisible subset ending at nums[i]. Also, initialize res to store the largest subset found so far.

3. Subset Calculation: Iterate over the array nums in reverse order. For each element nums[i], iterate over elements from i+1 to the end of the array. If nums[j] is divisible by nums[i], update dp[i] to be the combination of nums[i] and the largest divisible subset ending at nums[j]. Update res if the current subset is larger than the previously stored largest subset.

4. Return Result: Return the largest divisible subset stored in res.

Implement

    class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
      nums.sort()
      dp = [[num] for num in nums]
      res = dp[-1]
      for i in range(len(nums)-2,-1,-1):
          for j in range(i+1,len(nums)):
              if nums[j]%nums[i]==0 and 1+len(dp[j])>len(dp[i]):
                  dp[i] = [nums[i]] + dp[j]
          if len(dp[i])>len(res):
              res = dp[i]
      return res

    
       

    
    

Twitter  facebook  Email