# 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: