368. Largest Divisible Subset

Posted on Edited on In

368. Largest Divisible Subset

Description

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:

1
2
3
Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

Example 2:

1
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 .

Hints/Notes

Solution

Language: C++

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
35
36
37
38
39
40
41
42
class Solution {
public:
    vector<int> dp, from;
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        ranges::sort(nums);
        int n = nums.size();
        dp.resize(n, 0);
        from.resize(n, -1);
        int max_f = 0, max_idx = 0;
        for (int i = 0; i < n; i++) {
            int f = dfs(i, nums);
            if (f > max_f) {
                max_f = f;
                max_idx = i;
            }
        }
        vector<int> path;
        for (int i = max_idx; i >= 0; i = from[i]) {
            path.push_back(nums[i]);
        }
        return path;
    }

    int dfs(int idx, vector<int>& nums) {
        int& res = dp[idx];
        if (res) {
            return res;
        }
        for (int j = 0; j < idx; j++) {
            if (nums[idx] % nums[j]) {
                continue;
            }
            int f = dfs(j, nums);
            if (f > res) {
                res = f;
                from[idx] = j;
            }
        }
        res++;
        return res;
    }
};