🔥Dynamic Programming Approach || Sorting || C++
IntuitionAt first, my thought was to examine all possible subsets of the nums array and check if each subset satisfies the divisibility condition between its el
# Intuition
At first, my thought was to examine all possible subsets of the `nums` array and check if each subset satisfies the divisibility condition between its elements, keeping track of the largest such subset. However, generating all subsets has a time complexity of O(2^n), which is inefficient for larger arrays.

Then, I realized that if a number `a` is divisible by `b`, and `b` is divisible by `c`, then `a` is also divisible by `c`. This suggests sorting the array and building the subsets systematically. I considered using dynamic programming to solve this problem.

# Approach
1.  **Sort the array `nums`:** Sort the `nums` array in ascending order. This makes it easier to check the divisibility condition (if `a` is divisible by `b` and `a > b`, then `a` must appear after `b` in the sorted array).
2.  **Initialize the `dp` array:** Create a `dp` array of the same size as `nums`, where `dp[i]` will store the length of the largest divisible subset ending with `nums[i]`. Initialize all values in `dp` to 1 (each element by itself forms a divisible subset of size 1).
3.  **Initialize the `parent` array (optional but helpful):** Create a `parent` array of the same size as `nums`, where `parent[i]` will store the index of the element preceding `nums[i]` in the largest divisible subset ending with `nums[i]`. Initialize all values in `parent` to -1.
4.  **Iterate and update `dp`:** Iterate through the `nums` array from the beginning to the end (index `i`). For each `nums[i]`, iterate through all the elements before it (index `j` from 0 to `i-1`). If `nums[i]` is divisible by `nums[j]`, then we can extend the divisible subset ending with `nums[j]` by adding `nums[i]`. If `dp[j] + 1` is greater than `dp[i]`, update `dp[i] = dp[j] + 1` and `parent[i] = j`.
5.  **Find the maximum length and ending index:** After the loops, find the maximum value in the `dp` array and its corresponding index (`max_len` and `max_index`).
6.  **Reconstruct the subset:** Use the `parent` array to backtrack from `max_index` to build the largest divisible subset.

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

# Code
```cpp
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if (n == 0) {
            return {};
        }
        vector<int> dp(n, 1);
        vector<int> parent(n, -1);
        int max_len = 1;
        int max_index = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] % nums[j] == 0) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        parent[i] = j;
                        if (dp[i] > max_len) {
                            max_len = dp[i];
                            max_index = i;
                        }
                    }
                }
            }
        }

        vector<int> result;
        int curr = max_index;
        while (curr != -1) {
            result.push_back(nums[curr]);
            curr = parent[curr];
        }
        return result;
    }
};
['C++']