[Algorithm] Largest Divisible Subset

Largest Divisible Subset

Problem Statment

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:

nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)

Example 2:

nums: [1,2,4,8]

Result: [1,2,4,8]

Solution: Dynamic Programming & Sorting

Let's first look at the following equations:

Given that nums[i] > nums[j] > nums[k], if:

nums[i] % nums[j] == 0 and nums[j] % nums[k] == 0, then

nums[i] % nums[k] == 0 must also be true.

So let the state dp[j] of nums[j] be the count of divisible numbers less or equal to nums[j], and given nums[j] > nums[i] and nums[j] % nums[i] == 0, we can have dp[i] = dp[j] + 1. And we can keep track of the longest length of divisible subset.

The problem wants us to find out the full sequence, so when never we update dp[i] we shall keep track of the index j which leads to this index i. And when we are worst-casing the length, we need to keep track of the ending index i.

To get the full sequence, we simply backtrace from ending index back to the beginning of this sequence.

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class Solution { public: vector<int> largestDivisibleSubset(vector<int>& nums) { if (nums.size() < 2) return nums; sort(nums.begin(), nums.end()); int n = nums.size(); vector<int> dp(n, 1); vector<int> backtrace(n, -1); int endIdx = 0; for (int i=0; i<n; i++) { for (int j=0; j<i; j++) { if (nums[i] % nums[j] != 0) continue; if (dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; backtrace[i] = j; if (dp[i] > dp[endIdx]) { endIdx = i; } } } } vector<int> result; while (endIdx != -1) { result.push_back(nums[endIdx]); endIdx = backtrace[endIdx]; } return result; } };