# 368. Largest Divisible Subset

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,2,3]
</strong><strong>Output: [1,2]
</strong><strong>Explanation: [1,3] is also accepted.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [1,2,4,8]
</strong><strong>Output: [1,2,4,8]
</strong></code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
The fact that 1 4 9 10 16 24 32

1 4 16 32

The time we select 32, If it is a part we just have to check that
It is divisile by 16, Because 32 will be divisible by 4 and 1 

Sice 16 is divisible by them and so on 

So we can sort the array and check for Longest Divisible Subsequence

Exactly similar to LIS printing code
```

### Links

<https://leetcode.com/problems/largest-divisible-subset/description/>

### Video Links

<https://www.youtube.com/watch?v=gDuZwBW9VvM&ab_channel=takeUforward>

### Approach 1:

```
Trick to Print LIS
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        vector<int> dp(n,1);
        vector<int> hash(n);

        int last_index = 0;
        int maxi = 1;

        for(int index=0; index<n; index++){
            hash[index] = index;

            for(int prev=0; prev<index; prev++){
                if(arr[index] % arr[prev] == 0 and dp[index] < dp[prev]+1 ){
                    dp[index] = dp[prev] + 1;

                    hash[index] = prev;
                }

                if(dp[index] > maxi){
                    maxi = dp[index];
                    last_index = index;
                }
            }
        }

        vector<int> ans;
        ans.push_back(arr[last_index]);

        while(hash[last_index] != last_index){
            last_index = hash[last_index];
            ans.push_back(arr[last_index]);
        }

        return ans;
    }
};

```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###