368. Largest Divisible Subset #

Problem #

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.

Problem Summary #

Given a set nums consisting of distinct positive integers, find and return the largest divisible subset answer, such that every pair of elements (answer[i], answer[j]) in the subset satisfies:

• answer[i] % answer[j] == 0, or
• answer[j] % answer[i] == 0

If there are multiple valid solution subsets, return any one of them.

Solution Approach #

• Based on the problem’s data scale of 1000, we can estimate that this problem is very likely dynamic programming, with a time complexity of O(n^2). First sort the set, then use some smaller number as the base and continuously choose numbers that are divisible to add to the set. Following this idea, this problem is consistent with the classic LIS solution approach for problem 300. The only difference is that LIS chooses a larger number each time, while in this problem, besides choosing a larger number, there is one more check: whether this larger number can be divisible by all elements in the current set. Using this method, we can definitely find the largest set.
• The remaining problem is how to output the largest set. The set in this problem has the property of overlapping subsets. For example, the set [2,4,8,16] has length 4, and it must contain a subset of length 3, because any 3 numbers chosen from it also form a subset that satisfies the condition that the elements are mutually divisible. Similarly, it must also contain subsets of length 2 and length 1. Because of this property, we can use the data in the dp array to output the largest set. For example, for [2,4,6,8,9,13,16,40], dynamic programming can find that the largest set is [2,4,8,16]. After finding the one with length 4, then look for one with length 3: [2,4,8], [2,4,40]. In the largest set, the largest element is 16, so the set [2,4,40] is excluded because its largest element is greater than 16. Select the set [2,4,8], whose largest element is now 8. Continue in this way, filtering until the end, and then we can output the answer [16,8,4,2] for this largest set.

Code #

package leetcode

import "sort"

func largestDivisibleSubset(nums []int) []int {
	sort.Ints(nums)
	dp, res := make([]int, len(nums)), []int{}
	for i := range dp {
		dp[i] = 1
	}
	maxSize, maxVal := 1, 1
	for i := 1; i < len(nums); i++ {
		for j, v := range nums[:i] {
			if nums[i]%v == 0 && dp[j]+1 > dp[i] {
				dp[i] = dp[j] + 1
			}
		}
		if dp[i] > maxSize {
			maxSize, maxVal = dp[i], nums[i]
		}
	}
	if maxSize == 1 {
		return []int{nums[0]}
	}
	for i := len(nums) - 1; i >= 0 && maxSize > 0; i-- {
		if dp[i] == maxSize && maxVal%nums[i] == 0 {
			res = append(res, nums[i])
			maxVal = nums[i]
			maxSize--
		}
	}
	return res
}