Code Implementation

class Solution:
    def largestDivisibleSubset(self, nums):
        if not nums:
            return []
        nums.sort()
        n = len(nums)
        dp = [1] * n
        prev = [-1] * n
        max_idx = 0

        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            if dp[i] > dp[max_idx]:
                max_idx = i
        
        res = []
        while max_idx != -1:
            res.append(nums[max_idx])
            max_idx = prev[max_idx]
        return res[::-1]
      

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if (nums.empty()) return {};
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> dp(n, 1), prev(n, -1);
        int max_idx = 0;
        for (int i = 0; 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;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[max_idx]) max_idx = i;
        }
        vector<int> res;
        while (max_idx != -1) {
            res.push_back(nums[max_idx]);
            max_idx = prev[max_idx];
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
      

import java.util.*;
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        if (nums.length == 0) return new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        int[] prev = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);
        int max_idx = 0;
        for (int i = 0; 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;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[max_idx]) max_idx = i;
        }
        List<Integer> res = new ArrayList<>();
        while (max_idx != -1) {
            res.add(nums[max_idx]);
            max_idx = prev[max_idx];
        }
        Collections.reverse(res);
        return res;
    }
}
      

var largestDivisibleSubset = function(nums) {
    if (!nums.length) return [];
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const dp = new Array(n).fill(1);
    const prev = new Array(n).fill(-1);
    let max_idx = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] % nums[j] === 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > dp[max_idx]) max_idx = i;
    }
    const res = [];
    while (max_idx !== -1) {
        res.push(nums[max_idx]);
        max_idx = prev[max_idx];
    }
    return res.reverse();
};
      

Problem Description

Given a set of n distinct positive integers stored in the array nums, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: either Si % Sj == 0 or Sj % Si == 0. In other words, every pair in the subset must be divisible by each other.

You must return any one valid subset with the maximum possible size. Each element from nums may be used at most once in the subset.

Constraints:

• All elements in nums are positive and unique.
• There is at least one valid solution.
• Do not reuse numbers from nums.

Thought Process

At first glance, the problem seems related to finding subsets or sequences with a certain property—in this case, divisibility. A brute-force approach would be to generate all possible subsets and check each one for the divisibility condition, but this would be extremely inefficient for large arrays.

To optimize, we notice that if we sort the numbers, it's easier to check divisibility from smaller to larger numbers. This is because a larger number is more likely to be divisible by a smaller one. This insight allows us to use dynamic programming (DP), similar to the Longest Increasing Subsequence problem, but with divisibility as the condition instead of order.

The challenge is to build up the largest possible subset, maintaining for each element the length and previous element of the largest divisible subset ending at that element. This way, we can reconstruct the answer efficiently.

Solution Approach

We use dynamic programming with the following steps:

1. Sort the array nums in ascending order.
   • This helps because if a < b and b % a == 0, then a can precede b in the subset.
2. Initialize two arrays:
   • dp[i]: the size of the largest divisible subset ending with nums[i].
   • prev[i]: the index of the previous element in the subset ending at nums[i] (for reconstruction).
3. Dynamic Programming:
   • For each i from 0 to n-1:
   • For each j from 0 to i-1:
   • If nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
   • Update dp[i] = dp[j] + 1
   • Set prev[i] = j
   • Track the index max_idx where dp is largest.
4. Reconstruct the Subset:
   • Start from max_idx and follow prev backwards to build the subset.
   • Reverse the result to get the correct order.

This approach ensures that we only consider valid divisible chains and efficiently find the largest one.

Example Walkthrough

Suppose nums = [1, 2, 4, 8].

• After sorting: [1, 2, 4, 8]
• Initialize dp = [1, 1, 1, 1], prev = [-1, -1, -1, -1]
• For i = 1 (nums[1]=2):
  • 2 % 1 == 0 and dp[0]+1 > dp[1] → dp[1]=2, prev[1]=0
• For i = 2 (nums[2]=4):
  • 4 % 1 == 0 → dp[2]=2, prev[2]=0
  • 4 % 2 == 0 and dp[1]+1 > dp[2] → dp[2]=3, prev[2]=1
• For i = 3 (nums[3]=8):
  • 8 % 1 == 0 → dp[3]=2, prev[3]=0
  • 8 % 2 == 0 → dp[2]+1 > dp[3] → dp[3]=4, prev[3]=2
  • 8 % 4 == 0 → already handled
• The largest dp value is 4 at index 3. Trace back: 8 ← 4 ← 2 ← 1.
• The answer is [1, 2, 4, 8].

This example shows how the DP and traceback build up the largest divisible subset.

Time and Space Complexity

• Brute-force approach:
  • Would generate all subsets (2^n), checking each for divisibility (O(n^2) per subset).
  • Total: O(2^n * n^2), which is not feasible for large n.
• Optimized DP approach:
  • Sorting: O(n log n)
  • DP double loop: For each i, check all j < i → O(n^2)
  • Reconstructing the subset: O(n)
  • Total time complexity: O(n^2)
  • Space: O(n) for dp, prev, and the result subset

Summary

The Largest Divisible Subset problem can be solved efficiently by sorting the input and applying dynamic programming to build up the largest chain of divisible numbers. By keeping track of both the length and the previous index for each element, we can reconstruct the answer in linear time after the DP step. This approach is both elegant and efficient, turning a potentially exponential problem into a manageable O(n^2) solution.