Dp With Detailed Explanation 
🧮 Largest Divisible SubsetGiven a set of distinct positive integers, the goal is to return the largest subset such that for every pair (a, b) in the subset:
a %
# 🧮 Largest Divisible Subset

Given a set of **distinct positive integers**, the goal is to return the **largest subset** such that for **every pair** `(a, b)` in the subset:

- `a % b == 0` or `b % a == 0`

If there are multiple solutions, any one of them may be returned.

---
## Show Some Support Guys Soon Will Posting Roadmap ON How To Be 1900+ On Leetcode [INSTAGRAM](https://www.instagram.com/sumeetxcodeverse/)

## 📘 Intuition

This problem is a variation of the **Longest Increasing Subsequence (LIS)**, except the condition for inclusion is **divisibility** instead of increasing order.

By **sorting the array**, we guarantee that for any pair `(nums[i], nums[j])` with `i > j`, `nums[i]` is greater than or equal to `nums[j]`, making it easier to check `nums[i] % nums[j] == 0`.

This allows us to **build upon previously found valid subsets**. If `nums[i]` is divisible by `nums[j]`, then we can extend the subset ending at `nums[j]` to include `nums[i]`.

---

## 🛠️ Approach

### Step 1: Sort the array
- Sorting helps because a smaller number is more likely to divide a larger number.
- It also ensures that all potential divisors of a number appear before it.

### Step 2: Initialize the DP array
- Create a `dp` array where `dp[i]` represents the **length of the largest divisible subset** ending at index `i`.
- Initialize all values to `1` because each element is divisible by itself.

### Step 3: Fill the DP array
- Use two nested loops:
  - Outer loop: `i` from `1` to `n-1`
  - Inner loop: `j` from `0` to `i-1`
- If `nums[i] % nums[j] == 0`, and adding `nums[i]` would increase the length of the subset ending at `j`, update `dp[i]`.

### Step 4: Track the maximum length
- Keep track of the **maximum subset length** (`maxi`) and its corresponding number to help reconstruct the subset later.

### Step 5: Reconstruct the subset
- Traverse the array **in reverse**.
- If `dp[i] == maxi` and `nums[i]` divides the last added number (or it's the first one), add `nums[i]` to the result.
- Decrease `maxi` until we reconstruct the full subset.

---

## ⏱️ Time and Space Complexity

- **Time Complexity**:  
  $$O(n^2)$$  
  Two nested loops are used to compare all pairs of elements in the sorted array.

- **Space Complexity**:  
  $$O(n)$$  
  We use a `dp` array of size `n` and a result vector for the final answer.

---

## 💻 C++ Code

```cpp
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();

        if (n == 0) return {};

        sort(nums.begin(), nums.end());

        vector<int> dp(n, 1);         // dp[i]: length of largest subset ending at nums[i]
        vector<int> prev(n, -1);      // prev[i]: index of previous element in the subset
        int maxIdx = 0;               // index of last element of the largest subset

        // Build dp and prev arrays
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if (dp[i] > dp[maxIdx]) {
                maxIdx = i;
            }
        }

        // Reconstruct the subset
        vector<int> result;
        while (maxIdx >= 0) {
            result.push_back(nums[maxIdx]);
            maxIdx = prev[maxIdx];
        }

        reverse(result.begin(), result.end());
        return result;
    }
};

['Math', 'Dynamic Programming', 'Sorting', 'C++']