Largest Divisible Subset Problem
Description
LeetCode Problem 368.
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.
Sample C++ Code
Dynamic programming approach:
- We first sort the array so that we only have to check A[i] % A[j] when j < i.
- The vector dp[i] is the longest subset that satisfies the required conditions and ending at index i. The initial length of any subset is 1.
- The vector previous_index[i] stores the indices of previously included elements in this subset.
- For j < i < n, if A[i] % A[j] == 0 and dp[i] < dp[j] + 1, we add A[i] to the subsets that have last element as A[j].
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
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& A) {
int n = A.size();
if(n == 0) return {};
sort(A.begin(), A.end());
vector<int> dp(n, 1);
vector<int> previous_index(n, -1);
int max_ind = 0;
for(int i=1; i<n; i++) {
for(int j=0; j<i; j++) {
if(A[i]%A[j]==0 and dp[i] < dp[j] + 1) {
dp[i] = dp[j]+1;
previous_index[i] = j;
}
}
if(dp[i] > dp[max_ind]) {
max_ind = i;
}
}
vector<int> answer;
int t = max_ind;
while(t >= 0) {
answer.push_back(A[t]);
t = previous_index[t];
}
return answer;
}
};