# Largest Divisible Subset

## Problem Statement

Given a set of distinct positive integers, find the largest subset such that every pair `(Si, Sj)` of elements in this subset satisfies:

`Si % Sj = 0` or `Sj % Si = 0`

{% hint style="info" %}
If there are multiple solutions, returning any subset is fine.
{% endhint %}

## Testcases

```
Example 1:

Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)

Example 2:

Input: [1,2,4,8]
Output: [1,2,4,8]
```

## Problem Explanation

From a given set of unique positive integers, we must compare pairs of elements to see if either of the integers are divisible by the other. If the condition is satisfied, we create a subset with these integers. We must return the longest possible subset which can satisfy this condition. 

#### Example:

Consider the input array as: `[1, 2, 3]`

```
1 % 2 != 0, 2 % 1 = 0 (satisfied)
1 % 3 != 0, 3 % 1 = 0 (satisfied)
2 % 3 != 0, 3 % 2 != 0 (not satisfied)
Possible subsets: [1, 2], [1, 3]
```

## Prerequisite Knowledge

### Subset

A subset is a set of zero or more elements which is contained within a larger set of elements. The definition of a subset does not stipulate that the subset must maintain the relative order of the original set. That is, the order of the elements in the subset does not have to be sequentially equivalent to the set from which it has been derived.

#### Example

Let us consider the string **"coding"**. 

The sequence of elements in this string is as follows:

```
c o d i n g
1 2 3 4 5 6
```

A subset of the characters from the original set must contain only characters which belong to the original set but does not have to maintain the relative order in which they are present in that set.

**Correct Subset**: \[i, o, n]

```
i o n (valid elements)
4 2 5 
```

**Incorrect Subset**: \[c, s, n]

```
c s n (s is not in the original set
1 _ 5 
```

For a sequence of size n, we can have a total of (2^n) subsets.

Refer to the *Prerequisite Knowledge* section in **Is Subsequence** to understand the difference between a subsequence and a subset:

{% content-ref url="/pages/-M9SAvK0xLy5SmX2AytF" %}
[Is Subsequence](/june-leetcoding-challenge/week-2/is-subsequence.md)
{% endcontent-ref %}

### Dynamic Programming

Refer to the *Prerequisite Knowledge* section in **Coin Change 2**:

{% content-ref url="/pages/-M9K9cisnWuSztRUJF2y" %}
[Coin Change 2](/june-leetcoding-challenge/week-1/coin-change-2.md)
{% endcontent-ref %}

## Algorithm

### Bottom-Up DP Approach

1. Calculate the size of the input array and check if it is empty.
2. Sort the array in ascending order such that we only have to compare the value of nums\[j] % nums\[i] and not nums\[i] % nums\[j].
3. Create a vector to build the DP table with the length of the longest subset.
4. Create a vector to store and track the indices of previous elements in a subset such that when we build a bigger subset, we can include those elements.
5. Iterate through the input array such that j < i < n and add nums\[i] to the subset if and only if:

   &#x20;a. nums\[i] % nums\[j] == 0

   &#x20;b. If nums\[i] is added to the subset which ends with nums\[j], the length of the new subset is greater than the current subset.
6. Keep track of the previous indices in each iteration and the maximum index value.
7. Create a resultant vector to build the longest subset using the maximum index value and previous indices.

{% hint style="info" %}
Time Complexity: O(m\*n)
{% endhint %}

## Code

```cpp
vector<int> largestDivisibleSubset(vector<int>& nums) {
    int size = nums.size();
    
    if(size == 0) {
        return {};
    }
        
    // Sort the input vector such that i < j, so that we only have to compare nums[j] % nums[i]
    sort(nums.begin(), nums.end());
    
    // Create a vector to store the length of the longest substring
    // The initial length of any subset is 1
    vector<int> dp(size, 1);
    
    // Create a vector to store the indices of previously included elements in a subset which is being expanded
    vector<int> previous(size, -1);
    
    // Create a variable to keep track of the index of the longest substring
    int max = 0;
    
    // Iterate through the array elements such that j < i < n
    for(int i = 1; i < size; i++) {
        for(int j = 0; j < i; j++) {
            // If nums[i] % nums[j] = 0 and if the length of the subset ending with nums[j] becomes greater than the existing subset after adding nums[i]
            // We can add nums[i] to a subset with the last element being nums[j]
            if(nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                // Keep track of previous indices of i
                previous[i] = j;
            }
        }
        // Update the maximum index value
        if(dp[i] > dp[max]) {
            max = i;
        }
    }
    // Use a resultant vector to build the final subset
    vector<int> result;
    int index = max;
    while(index >= 0) {
        result.push_back(nums[index]);
        index = previous[index];
    }
    return result;
}
```


---

# 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://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-2/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.