Problem Overview

You are given a set of distinct positive integers nums.
Your task is to return the largest subset such that every pair (a, b) in the subset satisfies the condition:

a % b == 0 or b % a == 0

If there are multiple answers, return any of them.

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also a valid answer.

Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]

---

Intuition

The subset condition a % b == 0 or b % a == 0 implies a divisibility chain — each element in the subset must divide the next one.
This means sorting the array helps because smaller numbers are more likely to divide larger ones.

We can use Dynamic Programming (DP) to find the largest divisible subset by building it from smaller divisible subsets.

---

Approach: Dynamic Programming

Idea

1. Sort the array in ascending order.
2. For each number nums[i], we find the length of the largest divisible subset ending at nums[i].
3. Use a dp[i] array where:
   • dp[i] = size of the largest divisible subset ending with nums[i].
4. Maintain a prev[i] array to reconstruct the subset later.
5. Finally, find the index of the maximum value in dp and trace back using prev[] to build the answer.

---

Example Walkthrough

Let’s take:

nums = [1, 2, 4, 8]

After sorting: [1, 2, 4, 8]

i	nums[i]	dp[i]	prev[i]	Reason
0	1	1	-1	Base case
1	2	2	0	2 % 1 == 0
2	4	3	1	4 % 2 == 0
3	8	4	2	8 % 4 == 0

Max dp[i] = 4 at i = 3.
Reconstruct path using prev[] → [8, 4, 2, 1] → reverse → [1, 2, 4, 8].

---

Algorithm Steps

1. Sort the input array.
2. Initialize:
   • dp[i] = 1 for all i (each number is a subset of itself).
   • prev[i] = -1 (no predecessor initially).
3. For every i from 1 to n-1:
   • For every 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
4. Track the index maxIndex with the largest dp[i].
5. Reconstruct the subset by tracing back prev[] from maxIndex.

---

Java Code Implementation

import java.util.*;

public 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];      // dp[i] = size of largest subset ending at nums[i]
        int[] prev = new int[n];    // prev[i] = index of previous element in the chain

        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);

        int maxIndex = 0;

        // Build DP array
        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;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[maxIndex]) {
                maxIndex = i;
            }
        }

        // Reconstruct subset
        List<Integer> result = new ArrayList<>();
        int current = maxIndex;
        while (current >= 0) {
            result.add(nums[current]);
            current = prev[current];
        }

        Collections.reverse(result);
        return result;
    }
}

---

Complexity Analysis

Aspect	Analysis
Time Complexity	O(n²) because of the nested loops checking divisibility pairs
Space Complexity	O(n) for dp and prev arrays
Sorting Complexity	O(n log n) (dominated by O(n²) DP)

---

Alternative Approaches

1. Using Backtracking:
   • Try all subsets and check divisibility.
   • Exponential time O(2ⁿ) → inefficient for large inputs.
2. Optimized DP with HashMap:
   • Can be modified to store actual subsets instead of indices for easier reconstruction.

---

Key Takeaways

1. Sorting simplifies the divisibility relationship.
2. Dynamic Programming efficiently builds the solution using previous results.
3. Tracking predecessors allows easy reconstruction of the subset.
4. The approach is similar to Longest Increasing Subsequence (LIS) logic but with a divisibility condition instead of a strict order condition.