#   # 368. Largest Divisible Subset

## Dynamic programming might not always be the best

### Problem statement

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 * 10^9`.

• All the integers in `nums` are unique.

### Solution 1: Bruteforce with Dynamic programming

Note that the condition `a % b == 0` is called `a` is divisible by `b`. In mathematics, it can also be called `b` divides `a` and be written as `b | a`.

The symmetry of the divisibility criteria means it does not count the ordering of the `answer`. You could sort the vector `nums` before trying to find the longest subset `answer = [answer, answer, ..., answer[m]]` where `answer[i] | answer[j]` with all `0 <= i <= j <= m`.

Now assuming the `nums` were sorted. For each `i`, you need to find the largest subset `maxSubset[i]` starting from `nums[i]`. And the final answer is the largest one among them.

#### Example 3

``````Input: nums = [2, 4, 3, 9, 8].
Sorted nums = [2, 3, 4, 8, 9].
maxSubset = [2, 4, 8].
maxSubset = [3, 9].
maxSubset = [4, 8].
maxSubset = .
maxSubset = .
Output: [2, 4, 8].
``````

Note that for a sorted `nums`, if `nums[i] | nums[j]` for some `i < j`, then `maxSubset[j]` is a subset of `maxSubset[i]`.

For example, `maxSubset` is a subset of `maxSubset` in Example 3 because `nums = 2 | 4 = nums`.

That might lead to some unnecessary recomputing. To avoid it, you could use dynamic programming to store the `maxSubset[j]` you have already computed.

#### Code

``````#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

//! @brief compute the maxSubset[i] starting from nums[i]
//!         and store it to _map[i]
//! @note nums is sorted
vector<int> largestDivisibleSubsetOf(vector<int>& nums, int i,
unordered_map<int, vector<int> >& _map) {

if (_map.find(i) != _map.end()) {
return _map[i];
}
vector<int> maxSubset{nums[i]};
if (i == nums.size() - 1) {
_map.insert({i, maxSubset});
return maxSubset;
}
for (int j = i + 1; j < nums.size(); j++) {
if (nums[j] % nums[i] == 0) {
auto subset = largestDivisibleSubsetOf(nums, j, _map);
subset.push_back(nums[i]);
if (maxSubset.size() < subset.size()) {
maxSubset = subset;
}
}
}
_map.insert({i, maxSubset});
return maxSubset;
}
vector<int> largestDivisibleSubset(vector<int>& nums) {
if (nums.size() <= 1) {
return nums;
}
unordered_map<int, vector<int> > _map;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
auto maxSubset = largestDivisibleSubsetOf(nums, i, _map);
}
}
}
void printSolution(vector<int>& result) {
cout << "[";
for (auto& v : result) {
cout << v << ",";
}
cout << "]" << endl;
}
int main() {
vector<int> nums{2,1,3};
nums = {1,2,4,8};
}
``````
``````Output:
[2,1,]
[8,4,2,1,]
``````

#### Complexity

• Runtime: `O(2^N)`, where `N = nums.length`.

• Extra space: `O(N^2)`.

### Solution 2: Store only the representative of the `maxSubset`

In the brute-force solution above, you used a big `map` to log all `maxSubset[i]` though you need only the largest one at the end.

One way to save memory (and eventually improve performance) is just storing the representative of the chain relationship between the values `nums[i]` of the `maxSubset` through their indices mapping.

That means if `maxSubset[i] = [nums[i0] | nums[i1] | ... | nums[iN1]] | nums[iN]]`, you could log `pre[iN] = iN1`, ..., `prev[i1] = i0`.

Then all you need to find is only the last index `iN` of the largest `maxSubset`.

#### Example 3

``````Input: nums = [2, 4, 3, 9, 8].
sorted nums = [2, 3, 4, 8, 9].
pre = -1 (there is no nums[i] | nums).
pre = -1 (there is no nums[i] | nums).
pre = 0 (nums is the only divisor of nums).
pre = 2 (for the largest subset though nums and nums are both divisors of nums).
pre = 1 (nums is the only divisor of nums).
iN = 3 ([2 | 4 | 8] is the largest maxSubset).
Output: [8, 4, 2].
``````

#### Code

``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> largestDivisibleSubset(vector<int>& nums) {
if (nums.size() <= 1) {
return nums;
}
sort(nums.begin(), nums.end());
int maxSize = 0;    // the size of the resulting subset
int maxindex = 0;   // nums[maxindex] is the largest value of the resulting subset
vector<int> subsetSize(nums.size(), 1); // subsetSize[i] stores the size of the
//  largest subset having biggest number nums[i]
vector<int> pre(nums.size(), -1);       // pre[i] stores the previous index of
//  i in their largest subset
for (int i = 0; i < nums.size(); i++) {
// find the previous nums[j] that make subsetSize[i] largest
for (int j = i - 1; j >= 0; j--) {

if (nums[i] % nums[j] == 0 && subsetSize[j] + 1 > subsetSize[i]) {
subsetSize[i] = subsetSize[j] + 1;
pre[i] = j;
}
}
// update the largest subset
if (maxSize < subsetSize[i]) {
maxSize = subsetSize[i];
maxindex = i;
}
}
vector<int> result;
while (maxindex != -1) {
result.push_back(nums[maxindex]);
maxindex = pre[maxindex];
}
return result;
}
void printSolution(vector<int>& result) {
cout << "[";
for (auto& v : result) {
cout << v << ",";
}
cout << "]" << endl;
}
int main() {
vector<int> nums{2,1,3};
auto result = largestDivisibleSubset(nums);
printSolution(result);
nums = {1,2,4,8};
result = largestDivisibleSubset(nums);
printSolution(result);
}
``````
``````Output:
[2,1,]
[8,4,2,1,]
``````

#### Complexity

• Runtime: `O(N^2)`, where `N = nums.length`.

• Extra space: `O(N)`.

### Key takeaway

In this interesting problem, we use index mapping to simplify everything. That improves the performance in both runtime and memory.

### References

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.