🧩 Solving the Subset Puzzle with DP + Backtracking 🔄
🔗 Problem: Largest Divisible SubsetLeetCode 368 | Medium
Given a set of distinct positive integers nums, return the largest subset such that for every pair (i,
# 🔗 *Problem: Largest Divisible Subset* 
## *LeetCode 368 | Medium*

> Given a set of distinct positive integers `nums`, return the largest subset such that for every pair `(i, j)` in the subset, either `nums[i] % nums[j] == 0` or `nums[j] % nums[i] == 0`.

---

💡 **Approach: Dynamic Programming + Backtracking**  
The key idea is this:

👉 Once the array is **sorted**, if `nums[i]` divides `nums[j]`, then all elements that divide `nums[i]` will also divide `nums[j]`. This allows us to build a valid subset **backward**, like a reverse version of the Longest Increasing Subsequence (LIS) — but with divisibility instead of numerical order.

---

🔍 **Code Explanation (C++):**

```cpp
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end()); // Step 1: Sort to simplify divisibility checks

        vector<int> count(n);  // DP: count[i] = length of largest subset starting at i
        vector<int> nextt(n);  // Backtracking: nextt[i] = next index in the subset chain

        int maxi = 0;          // Index of the largest subset start

        // Step 2: DP from the end to the beginning
        for (int i = n - 1; i >= 0; i--) {
            count[i] = 1;      // Base case: each element is a subset of size 1
            nextt[i] = -1;     // -1 indicates end of the subset

            // Step 3: Check all larger elements for valid division
            for (int j = i + 1; j < n && n - j + 1 > count[i]; j++) {
                if (nums[j] % nums[i] != 0) continue;

                if (count[j] + 1 > count[i]) {
                    count[i] = count[j] + 1;
                    nextt[i] = j; // Store the next element in the chain
                }
            }

            // Step 4: Track the global maximum
            if (count[maxi] < count[i]) {
                maxi = i;
            }
        }

        // Step 5: Backtrack to reconstruct the subset
        vector<int> answer;
        int i = maxi;
        while (i != -1) {
            answer.push_back(nums[i]);
            i = nextt[i];
        }

        return answer;
    }
};
```

---

🧩 **Key Concepts:**

- **Sorting:**  
  Sorting the array ensures that divisibility can be checked consistently from the smallest to the largest element.

- **DP Tabulation:**  
  - `count[i]`: The length of the largest divisible subset starting at index `i`.  
  - `nextt[i]`: Points to the next index in the chain to enable reconstruction of the subset.

- **Backtracking:**  
  After filling the DP arrays, backtracking via `nextt[]` allows us to reconstruct the largest divisible subset.

---

🕰️ **Time Complexity:**

- **Sorting:** O(n log n)  
- **DP Traversal:** O(n²) (due to the nested loop)  
- **Overall:** O(n²)

📦 **Space Complexity:**  
O(n) for the `count[]`, `nextt[]`, and final `answer[]` vectors.

---

🤔 **Why I Like This Approach:**

Even though this version only beats about **31%** of submissions in terms of runtime, it's:
- **Readable** and **easy to understand** for learners.
- A **solid foundation** for further optimizations.
- A great example of applying classic **dynamic programming + backtracking** techniques, similar to how one would approach the Longest Increasing Subsequence problem.

---

🧠 **TL;DR:**  
Sort the array → use tabulation to compute max subset lengths → backtrack using `nextt[]` to reconstruct the subset.  
It’s a dynamic programming twist on the Longest Increasing Subsequence — but with **division** as the connecting factor.

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