Python - DP - Beat 90%
CodePlease Up Vote ⬆️⬆️ If it is helpfulApproachWe use Dynamic Programming to build the largest divisible subset.Steps:
Sort the array: Ensures we only need to
# Code

```python3
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        dp = [[num] for num in nums]

        for i in range(len(nums)):
            for j in range(i):
                if nums[i] % nums[j] == 0 and len(dp[j]) + 1 > len(dp[i]):
                    dp[i] = dp[j] + [nums[i]]

        return max(dp, key=len)
```

## Please Up Vote ⬆️⬆️ If it is helpful  

---

# Approach  

We use **Dynamic Programming** to build the largest divisible subset.

### Steps:
1. **Sort the array:** Ensures we only need to check divisibility in one direction (`nums[i] % nums[j] == 0`).
2. **Initialize `dp` array:**  
   Each element `dp[i]` stores the largest divisible subset ending with `nums[i]`.
3. **Update DP array:**  
   For each pair `i > j`, if `nums[i] % nums[j] == 0` and extending `dp[j]` makes `dp[i]` longer, we update it.
4. **Return the longest subset** from `dp` using `max(dp, key=len)`.

---

# Complexity Analysis  
- **Time Complexity:** $$O(n^2)$$  
- **Space Complexity:** $$O(n^2)$$ (for storing all subsets)  
Efficient for input size `n ≤ 1000`.
['Dynamic Programming', 'Python3']