DP + Sorting |✅With Images |🚶‍♂️Example Walkthrough | C++ | Python | Java
🤔 Understanding the Question
We're given a set of numbers and we need to find the largest subset such that each number in that group is divisible by another in
# 🤔 Understanding the Question
- We're given a set of numbers and we need to find the largest subset such that each number in that group is divisible by another in the group i.e 
```css
answer[i] % answer[j] == 0, or
answer[j] % answer[i] == 0
```
---

# 💡 Approach
- We firstly need to **sort the array** as it'll help us in finding the largest possible subset & simplifying divisibility checks.
- We then need to create a `dp` array where `dp[i]` stores the **longest subset upto this index**.
- And a `prev` array which keeps track of the **previous index in the subset** chain.
- We then traverse the input array and for every index where the condition `nums[j] % nums[i] == 0` holds we **update** our `dp` and `prev` array to check if the subset can be made longer.
- We also use a pointer `maxi` to track the **end of the longest subset so far**.
- Lastly we need to **backtrack** using `prev` from `maxi` to store the **numbers which are a part of the longest subset** we found.
- **Time Complexity :** $$O(n^2)$$
- **Space Complexity :** $$O(n)$$
---
# 🚶‍♂️ Example Walkthrough
- Let's take an example for the array ⟶ `[1, 2, 4, 8]`
- This is how our **initial setup** looks like ⟶

<img src="https://assets.leetcode.com/users/images/799cc6a5-a2b3-4c09-8883-99a8b61233ca_1743899258.869026.png" width="500"/>


- Let's start traversing from **1 to n** in our `i` loop and from **0 to i** in our `j` loop to check the conditions given in the question now. 
- At `i = 1` & `j = 0`,

![image.png](https://assets.leetcode.com/users/images/1959e247-d365-4914-8073-54951876e819_1743899920.134184.png)
- For `i = 2` & `j = 0`,

![image.png](https://assets.leetcode.com/users/images/f3ecf7a7-0388-441f-a803-4e2306c93d55_1743900107.6410182.png)
- For `i = 2` & `j = 1`,

![image.png](https://assets.leetcode.com/users/images/778df24f-05ce-4413-9f0c-04b1d7684c5a_1743900190.1583822.png)
- For `i = 3` & `j = 0`,

![image.png](https://assets.leetcode.com/users/images/5eec8e71-7892-459b-a237-adb1820e9998_1743900269.5799835.png)
- For `i = 3` & `j = 1`,

![image.png](https://assets.leetcode.com/users/images/05b99702-5b50-4f23-8610-383f80a5f4a1_1743900345.2050982.png)
- For `i = 3` & `j = 2`,

![image.png](https://assets.leetcode.com/users/images/d007dd45-b08d-4494-aa80-0a37db4bacad_1743902871.1747074.png)


- Here is the above testcase dry run in tabular format,

| i | nums[i] | j | nums[j] | dp[i] before | dp[j] + 1 | dp[i] after | prev[i] |
|---|---------|---|---------|---------------|------------|--------------|----------|
| 1 |    2    | 0 |    1    |       1       |     2      |      2       |    0     |
| 2 |    4    | 0 |    1    |       1       |     2      |      2       |    0     |
| 2 |    4    | 1 |    2    |       2       |     3      |      3       |    1     |
| 3 |    8    | 0 |    1    |       1       |     2      |      2       |    0     |
| 3 |    8    | 1 |    2    |       2       |     3      |      3       |    1     |
| 3 |    8    | 2 |    4    |       3       |     4      |      4       |    2     |

- And lastly, here is how our backtracking works on `prev` array,
```
Start at index 3 (nums[3] = 8)
→ prev[3] = 2 → nums[2] = 4  
→ prev[2] = 1 → nums[1] = 2  
→ prev[1] = 0 → nums[0] = 1  
→ prev[0] = -1 → stop
```
---
# 💻 Implementation
```cpp []
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> dp(nums.size(), 1), prev(nums.size(), -1);
        int maxi = 0;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[maxi]) maxi = i;
        }
        vector<int> res;
        for (int i = maxi; i >= 0; i = prev[i]) {
            res.push_back(nums[i]);
        }
        return res;
    }
};
```
```Python []
class Solution(object):
    def largestDivisibleSubset(self, nums):
        nums.sort()
        dp = [1] * len(nums)
        prev = [-1] * len(nums)
        maxi = 0
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            if dp[i] > dp[maxi]:
                maxi = i
        res = []
        i = maxi
        while i >= 0:
            res.append(nums[i])
            i = prev[i]
        return res
```
```Java []
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int[] dp = new int[nums.length];
        int[] prev = new int[nums.length];
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);
        int maxi = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[maxi]) maxi = i;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = maxi; i >= 0; i = prev[i]) {
            res.add(nums[i]);
        }
        return res;
    }
}
```
<img src="https://assets.leetcode.com/users/images/cc496d84-0690-4377-b8a3-f621f326df8f_1742786890.68028.png" width="400">
['Dynamic Programming', 'Sorting', 'Python', 'C++', 'Java']