# Largest Divisible Subset
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/largest-divisible-subset)
Canonical: https://scaleengineer.com/dsa/problems/largest-divisible-subset
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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:**

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

**Example 2:**

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

**Constraints:**

* `1 <= nums.length <= 1000`
* `1 <= nums[i] <= 2 * 109`
* All the integers in `nums` are **unique**.

# Approaches
## Brute Force by Generating All Subsets
This naive approach involves generating every possible subset of the input array `nums`. For each subset, we check if it satisfies the divisible subset property, where for any pair of elements, one must divide the other. We keep track of the largest valid subset found.
**Time:** O(2^N * N^2). There are `2^N` subsets. For each subset of size `K`, the validation check takes `O(K^2)` pairwise comparisons. The average subset size is `N/2`, leading to this complexity. · **Space:** O(N). The space is required to store the `currentSubset` and the `largestSubset` found. Each can have a maximum size of `N`.
**Pros:** Conceptually simple and easy to understand.
**Cons:** Extremely inefficient.; Feasible only for very small `N` (e.g., N < 20).; Will result in a 'Time Limit Exceeded' error for the given problem constraints.
### Explanation
The core idea is to explore the entire solution space. The number of subsets of a set with `N` elements is `2^N`. We can represent each subset using a bitmask of length `N`. For each bitmask, we construct the corresponding subset. Then, we perform a validation check on this subset. The validation involves iterating through all pairs of numbers in the subset and checking the divisibility condition. If a subset is valid, we compare its size with the largest one found so far and update if necessary. While simple to conceptualize, this method is computationally expensive and impractical for the given constraints.
### Algorithm
*   Initialize an empty list `largestSubset` to store the result.
*   Let `N` be the number of elements in `nums`.
*   Loop through all integers from `0` to `2^N - 1`. Each integer `i` acts as a bitmask.
*   For each `i`, create a `currentSubset`:
    *   Iterate from `j = 0` to `N-1`.
    *   If the `j`-th bit of `i` is set, add `nums[j]` to `currentSubset`.
*   Check if `currentSubset` is a valid divisible subset:
    *   Assume it's valid (`isValid = true`).
    *   Iterate through all pairs of elements `(a, b)` in `currentSubset`.
    *   If `a % b != 0` and `b % a != 0`, set `isValid = false` and break the loops.
*   If `isValid` is true and `currentSubset.size() > largestSubset.size()`, update `largestSubset = currentSubset`.
*   After checking all `2^N` possibilities, return `largestSubset`.

## Dynamic Programming
A much more efficient approach is to use dynamic programming, which is well-suited for problems with optimal substructure. The strategy is similar to solving the Longest Increasing Subsequence (LIS) problem. By first sorting the input array, we can build the solution iteratively.
**Time:** O(N^2). Sorting the array takes `O(N log N)`. The nested loops for the DP calculation take `O(N^2)`. Reconstructing the path takes `O(N)`. The overall complexity is dominated by the `O(N^2)` part. · **Space:** O(N). We use two arrays, `dp` and `prev`, each of size `N`. The list for the result also requires up to `O(N)` space.
**Pros:** Efficient enough to pass for the given constraints.; Guarantees finding the largest divisible subset.; It's a standard and well-understood dynamic programming pattern.
**Cons:** Requires extra space for DP and predecessor arrays.; The `O(N^2)` time complexity might be a bottleneck for significantly larger inputs beyond the problem's constraints.
### Explanation
The key insight is that if we sort the input array `nums`, any valid divisible subset, when sorted, will have the property that each element is divisible by the preceding element. This transforms the problem into finding the longest such sequence.

We use a DP array, `dp`, where `dp[i]` stores the size of the largest divisible subset that ends with the element `nums[i]`. To compute `dp[i]`, we look at all previous elements `nums[j]` (where `j < i`). If `nums[i]` is divisible by `nums[j]`, it means we can potentially extend the subset ending at `nums[j]`. We choose the `j` that gives the maximum length, so `dp[i] = 1 + max(dp[j])` for all valid `j`.

To reconstruct the actual subset, we use an auxiliary array, `prev`, where `prev[i]` stores the index of the element that precedes `nums[i]` in the longest divisible subset. After filling the `dp` and `prev` arrays, we find the index corresponding to the maximum value in `dp` and backtrack using the `prev` array to build the result.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return new ArrayList<>();
        }

        Arrays.sort(nums);

        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int[] prev = new int[n];
        Arrays.fill(prev, -1);

        int maxIndex = 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[maxIndex]) {
                maxIndex = i;
            }
        }

        List<Integer> result = new ArrayList<>();
        int k = maxIndex;
        while (k != -1) {
            result.add(nums[k]);
            k = prev[k];
        }

        return result;
    }
}
```
### Algorithm
*   If the input array `nums` is empty, return an empty list.
*   Sort the array `nums` in non-decreasing order.
*   Initialize an integer array `dp` of size `N`, with all elements set to `1`. `dp[i]` will store the length of the largest divisible subset ending at `nums[i]`.
*   Initialize an integer array `prev` of size `N`, with all elements set to `-1`. `prev[i]` will store the index of the previous element in the largest divisible subset ending at `nums[i]`.
*   Initialize `maxIndex = 0` to track the index of the last element of the largest subset found so far.
*   Iterate through `nums` from `i = 0` to `N-1`:
    *   For each `i`, iterate from `j = 0` to `i-1`:
        *   If `nums[i]` is divisible by `nums[j]` and `dp[j] + 1` is greater than `dp[i]`:
            *   Update `dp[i] = dp[j] + 1`.
            *   Update `prev[i] = j`.
    *   If `dp[i]` is greater than `dp[maxIndex]`, update `maxIndex = i`.
*   Reconstruct the result list:
    *   Initialize an empty list `result`.
    *   Start with `k = maxIndex`.
    *   While `k` is not `-1`:
        *   Add `nums[k]` to `result`.
        *   Update `k = prev[k]`.
*   Return the `result` list.

# Solutions
### Java

```java
class Solution { public List < Integer > largestDivisibleSubset ( int [] nums ) { Arrays . sort ( nums ); int n = nums . length ; int [] f = new int [ n ]; Arrays . fill ( f , 1 ); int k = 0 ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = 0 ; j < i ; ++ j ) { if ( nums [ i ] % nums [ j ] == 0 ) { f [ i ] = Math . max ( f [ i ], f [ j ] + 1 ); } } if ( f [ k ] < f [ i ]) { k = i ; } } int m = f [ k ]; List < Integer > ans = new ArrayList <>(); for ( int i = k ; m > 0 ; -- i ) { if ( nums [ k ] % nums [ i ] == 0 && f [ i ] == m ) { ans . add ( nums [ i ]); k = i ; -- m ; } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  vector<int> largestDivisibleSubset(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int f[n];
    int k = 0;
    for (int i = 0; i < n; ++i) {
      f[i] = 1;
      for (int j = 0; j < i; ++j) {
        if (nums[i] % nums[j] == 0) {
          f[i] = max(f[i], f[j] + 1);
        }
      }
      if (f[k] < f[i]) {
        k = i;
      }
    }
    int m = f[k];
    vector<int> ans;
    for (int i = k; m > 0; --i) {
      if (nums[k] % nums[i] == 0 && f[i] == m) {
        ans.push_back(nums[i]);
        k = i;
        --m;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def largestDivisibleSubset ( self , nums : List [ int ]) -> List [ int ]: nums . sort () n = len ( nums ) dp = [ 0 ] * n parent = [ 0 ] * n max_index , max_length = 0 , 0 for i in range ( n - 1 , - 1 , - 1 ): for j in range ( i , n ): # note: not i+1, for i==j length is 1 if nums [ j ] % nums [ i ] == 0 and dp [ i ] < 1 + dp [ j ]: dp [ i ] = 1 + dp [ j ] parent [ i ] = j if dp [ i ] > max_length : max_length = dp [ i ] max_index = i res = [] for _ in range ( max_length ): res . append ( nums [ max_index ]) max_index = parent [ max_index ] return res ################ class Solution : def largestDivisibleSubset ( self , nums : List [ int ]) -> List [ int ]: nums . sort () n = len ( nums ) f = [ 1 ] * n k = 0 for i in range ( n ): for j in range ( i ): if nums [ i ] % nums [ j ] == 0 : f [ i ] = max ( f [ i ], f [ j ] + 1 ) if f [ k ] < f [ i ]: k = i m = f [ k ] i = k ans = [] while m : if nums [ k ] % nums [ i ] == 0 and f [ i ] == m : ans . append ( nums [ i ]) k , m = i , m - 1 i -= 1 return ans
```