🔥🔥||Beats 100% in most||Easy solution using||Dynamic programming|Sorting|Recursion||🔥🔥
Intuition💡We are asked to find the largest subset of numbers such that every pair in the subset satisfies the divisibility condition. This resembles the Longest
# Intuition💡
We are asked to find the largest subset of numbers such that every pair in the subset satisfies the divisibility condition. This resembles the Longest Increasing Subsequence (LIS) problem, but instead of checking if one number is greater than another, we check if one number divides the other. Sorting the array helps ensure that for any number, all its divisors come before it in the list.

---


# Approach🚀
1.)Sort the input array to ensure divisibility relations can be checked in one direction (i.e., from smaller to larger).
2.)Use recursion with memoization (a DP table dp[i][prev+1]) where i is the current index and prev is the index of the last included element in the subset.
3.)At each step, we decide:
Take the current element if it's divisible by the previous element.
Not take the current element and move to the next.
4.)Store the result in the DP table to avoid recomputation.
5.)After the DP table is filled, reconstruct the subset using the computed results by following the decisions that led to the optimal value.

---


# Complexity⌚
- Time complexity:
O(n^2)

- Space complexity:
O(n^2)

---

> # ***PLEASE UPVOTE IF THIS HELPED YOU LEARN!***

---

ALL CODES ARE HERE🍵🐍C➕➕C#️⃣💎
✅HAPPY LEETCODING!
# 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;
    }
};
```
```python3 []
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        dp = [1] * n
        max_size, max_index = 1, 0

        for i in range(1, n):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    dp[i] = max(dp[i], dp[j] + 1)
                    if dp[i] > max_size:
                        max_size = dp[i]
                        max_index = i

        result = []
        num = nums[max_index]
        for i in range(max_index, -1, -1):
            if num % nums[i] == 0 and dp[i] == max_size:
                result.append(nums[i])
                num = nums[i]
                max_size -= 1

        return result
```
```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]);
            if (prev[i] == -1) break;
        }
        return res;
    }
}
```
```javascript []
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var largestDivisibleSubset = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const dp = new Array(n).fill(1);
    const prev = new Array(n).fill(-1);

    let maxLen = 1, maxIndex = 0;

    for (let i = 1; i < n; i++) {
        for (let 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] > maxLen) {
            maxLen = dp[i];
            maxIndex = i;
        }
    }

    const res = [];
    while (maxIndex !== -1) {
        res.unshift(nums[maxIndex]);
        maxIndex = prev[maxIndex];
    }

    return res;
};
```
```C# []
public class Solution {
    public IList<int> LargestDivisibleSubset(int[] nums) {
        int n = nums.Length;
        Array.Sort(nums);

        int[] dp = new int[n];    
        int[] prev = new int[n];   
        Array.Fill(dp, 1);
        Array.Fill(prev, -1);

        int maxIndex = 0;

        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[maxIndex]) {
                maxIndex = i;
            }
        }

        List<int> result = new List<int>();
        int k = maxIndex;
        while (k != -1) {
            result.Add(nums[k]);
            k = prev[k];
        }

        result.Reverse(); 
        return result;
    }
}
```
```Ruby []
class Numeric
    def max(v) = (self < v ? v : self)
end

def largest_divisible_subset(nums)
    ms, mi = 1, 0
    dp = nums.sort!.each_with_index.each_with_object(Array.new(nums.size, 1)) {|(v, i), dp|
        i.times {|j|
            next unless (v % nums[j]).zero?
            ms, mi = dp[i], i if ((dp[i] = dp[i].max(dp[j] + 1)) > ms)
        }
    }
    mn = nums[mi]
    mi.downto(0).each_with_object([]) {|i, r|
        next unless ((mn % nums[i]).zero? && dp[i] == ms)
        r << (mn = nums[i])
        ms -= 1
    }
end
```
```Rust []
impl Solution {
  pub fn largest_divisible_subset(mut nums: Vec<i32>) -> Vec<i32> {
    nums.sort_unstable();

    let mut res = vec![Vec::new(); nums.len()];
    for i in 0 .. nums.len() {
      res[i].push(nums[i]);
    }

    for i in 1 .. nums.len() {
      for j in 0 .. i {
        if (nums[i] % nums[j] == 0) && (res[i].len() < res[j].len() + 1) {
          let mut tmp = res[j].to_vec();
          tmp.push(nums[i]);
          res[i] = tmp;
        }
      }
    }

    let (mut max_len, mut max_pos) = (0, 0);
    for i in 0 .. res.len() {
      if res[i].len() > max_len {
        max_len = res[i].len();
        max_pos = i;
      }
    }
    return res[max_pos].to_vec();
  }
}
```

![plez upvote.png](https://assets.leetcode.com/users/images/b6d869ef-6e51-45bb-828c-f85cee071b16_1743911309.8668659.png)


['Dynamic Programming', 'Recursion', 'Sorting', 'C++', 'Java', 'Python3', 'Rust', 'Ruby', 'JavaScript', 'C#']