# 368. Largest Divisible Subset
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:
Si % Sj = 0 or Sj % Si = 0
.
If there are multiple solutions, return any subset is fine.
Example 1:
Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)
Example 2:
Input: [1,2,4,8]
Output: [1,2,4,8]
# Solution
Approach 1: DP -- order the nums, and for each num, store the size of subset and a reference to the previous item in the subset. Time: N^2
.
# Code (Python)
Approach 1:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
if not nums:
return []
nums.sort()
# subsets stores (previous_index_in_subset, length_of_local_largest_subset)
subsets = [(-1, 1) for i in range(len(nums))]
largest_subset_index = 0
for i in range(1, len(nums)):
for j in range(i):
if nums[i] % nums[j] == 0 and subsets[i][1] < subsets[j][1] + 1:
subsets[i] = (j, subsets[j][1] + 1)
if subsets[largest_subset_index][1] < subsets[i][1]:
largest_subset_index = i
# backtrack to retrieve the entire subset
subset = []
index = largest_subset_index
while index != -1:
subset.append(nums[index])
index = subsets[index][0]
return subset[::-1]
# Code (C++)
Approach 1:
Approach 2: