🔥Beats 95% 🚀🔥 || Smaller code in C...P...J
🧠 IntuitionThe problem asks for the largest subset of numbers such that every pair in the subset satisfies the condition nums[i] % nums[j] == 0 or nums[j] % num
# 🧠 Intuition
The problem asks for the **largest subset** of numbers such that every pair in the subset satisfies the condition `nums[i] % nums[j] == 0` or `nums[j] % nums[i] == 0`.  
This sounds similar to the **Longest Increasing Subsequence** problem, where we can build up solutions using dynamic programming. By sorting the array, we ensure a natural ordering that helps in checking divisibility efficiently.

---

# 🛠️ Approach
1. 📊 **Sort** the array to simplify checking for divisibility.
2. 🧩 Use a **DP array** `store[i]` to keep the size of the largest divisible subset ending at index `i`.
3. 🔗 Use a `parent` array to keep track of the **previous index** in the subset chain.
4. 🔁 For each `i`, loop through all previous indices `j`, and if `nums[i] % nums[j] == 0`, try to update `store[i]` and `parent[i]`.
5. 📈 Track the **maximum size** and the **ending index** of the optimal subset.
6. 🔄 Reconstruct the result by backtracking using the `parent` array.

---
# ⏱️ Complexity
- **Time complexity:**  
  $$O(n^2)$$ — We compare each pair of elements once.

- **Space complexity:**  
  $$O(n)$$ — We use extra arrays for `store`, `parent`, and `ans`.

---

![Screenshot 2025-04-06 111717.png](https://assets.leetcode.com/users/images/d35aa07b-e102-45ec-886a-eee808cf2304_1743918582.0175903.png)


# 💻 Code
```cpp []
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {

        sort(nums.begin(), nums.end());
        int n = nums.size(), maxIdx = -1, maxs = 1;
        if (n == 1) return nums;
        vector<int> store(nums.size(), 1), parent(n, -1);

        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0) {
                    if (store[i] < store[j] + 1) {
                        store[i] = store[j] + 1;
                        parent[i] = j;
                    }

                    if (maxs < store[i]) {
                        maxs = store[i];
                        maxIdx = i;
                    }
                }
            }
        }
        vector<int> ans;
        if (maxIdx == -1) return {nums[0]};
        
        while (maxIdx != -1) {
            ans.push_back(nums[maxIdx]);
            maxIdx = parent[maxIdx];
        }
        return ans;
    }
};
```
``` Python []
class Solution:
    def largestDivisibleSubset(self, nums):
        nums.sort()
        n = len(nums)
        dp = [1] * n
        parent = [-1] * n
        max_len = 1
        max_index = 0

        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    parent[i] = j
            if dp[i] > max_len:
                max_len = dp[i]
                max_index = i

        result = []
        while max_index != -1:
            result.append(nums[max_index])
            max_index = parent[max_index]

        return result
```
``` Java []
import java.util.*;

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] dp = new int[n];
        int[] parent = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(parent, -1);

        int maxLen = 1, maxIdx = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                maxIdx = i;
            }
        }

        List<Integer> result = new ArrayList<>();
        while (maxIdx != -1) {
            result.add(nums[maxIdx]);
            maxIdx = parent[maxIdx];
        }

        return result;
    }
}
```
``` Javascript []
var largestDivisibleSubset = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const dp = Array(n).fill(1);
    const parent = Array(n).fill(-1);

    let maxLen = 1, maxIdx = 0;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] % nums[j] === 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            maxIdx = i;
        }
    }

    const result = [];
    while (maxIdx !== -1) {
        result.push(nums[maxIdx]);
        maxIdx = parent[maxIdx];
    }

    return result;
};
```
![upvote-agree.gif](https://assets.leetcode.com/users/images/5b45b3ac-ddb2-4486-90e1-12ac52b47907_1743918541.0261214.gif)

['Python', 'C++', 'Java', 'JavaScript']