SImple And Easy Solution | o(n) Complexity for Space | o(n^2) for Time
Intuition💡 Intuition:
The problem is essentially a variation of the Longest Increasing Subsequence (LIS), but instead of increasing order, we're checking if ele
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
💡 Intuition:
The problem is essentially a variation of the Longest Increasing Subsequence (LIS), but instead of increasing order, we're checking if elements are divisible.

Key Observations:
If a number a divides a number b, then all multiples of a could potentially form a chain.

Sorting the array makes it easier to apply the divisible condition, as smaller numbers will come before their potential multiples.

For every number, we want to find the largest subset ending with it that satisfies the condition

# Approach
<!-- Describe your approach to solving the problem. -->
🧠 Approach:
Step-by-step:
Sort the array: This ensures all possible divisors come before a number.

cpp
Copy
Edit
sort(nums.begin(), nums.end());
Initialize helper structures:

freq[i]: Stores the length of the largest divisible subset ending at nums[i].

temp[i]: Stores the index of the previous number in the subset (used for backtracking the result).

maxi, idx: Track the maximum size of subset found and the ending index.

cpp
Copy
Edit
vector<int> temp(n);
unordered_map<int, int> freq;
Dynamic Programming logic:

For each number nums[i], check all previous numbers nums[j] where j < i.

If nums[i] % nums[j] == 0, it means they are divisible.

Then, update the maximum length of subset ending at i if freq[nums[j]] + 1 is greater.

Update temp[i] to point to j for backtracking the path later.

cpp
Copy
Edit
if (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)
Backtrack to find the subset:

Start from the index of the maximum value (idx) and keep moving back using temp.

while (idx >= 0) {
    ans.push_back(nums[idx]);
    if (temp[idx] == idx) break;
    idx = temp[idx];
}
Return the result subset:

The answer may be in reverse order, but still valid.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n=nums.size();
        vector<int>temp(n);
        unordered_map<int,int>freq;
        for(int i=0;i<n;i++){
            temp[i]=i;
            freq[nums[i]]=1;
        }
        int maxi=0,idx=0;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]%nums[j]==0 || nums[j]%nums[i]==0){
                    int val=freq[nums[j]]+1;
                    if(maxi<val){
                        maxi=val;
                        idx=i;
                    }
                    if(freq[nums[i]]<=val){
                        freq[nums[i]]=val;
                        temp[i]=j;
                    }
                }
            }
        }

        vector<int>ans;
        while(idx>=0){
            ans.push_back(nums[idx]);
            if(temp[idx]==idx)break;
            idx=temp[idx];
        }
        return ans;
    }
};
```
['Array', 'Math', 'Dynamic Programming', 'Sorting', 'C++']