# 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

###


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-lis/368.-largest-divisible-subset.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.