Given a set of distinct positive integers nums, find the largest subset such that every pair (Si, Sj) satisfies Si % Sj == 0 or Sj % Si == 0.
Input: [1,2,3] → Output: [1,2]Input: [1,2,4,8] → Output: [1,2,4,8]
Sort the array. dp[i] = length of largest divisible subset ending at i. parent[] tracks path. When nums[i] % nums[j] == 0, we can extend j's subset.
- Sort nums.
- dp[i]=1, parent[i]=-1 initially.
- For i from 1 to n-1: for j from 0 to i-1: if nums[i]%nums[j]==0 and dp[j]+1>dp[i]: dp[i]=dp[j]+1, parent[i]=j.
- Find max index, trace back using parent[] to reconstruct subset.
import java.util.*;
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int[] dp = new int[n], parent = new int[n];
Arrays.fill(dp, 1); Arrays.fill(parent, -1);
int maxIdx = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1; parent[i] = j;
}
}
if (dp[i] > dp[maxIdx]) maxIdx = i;
}
List<Integer> res = new ArrayList<>();
for (int i = maxIdx; i >= 0; i = parent[i]) {
res.add(nums[i]);
if (parent[i] == -1) break;
}
return res;
}
}
- Time Complexity: O(N^2)
- Space Complexity: O(N)