<p>Given a set of <strong>distinct</strong> positive integers <code>nums</code>, return the largest subset <code>answer</code> such that every pair <code>(answer[i], answer[j])</code> of elements in this subset satisfies:</p>

<ul>
	<li><code>answer[i] % answer[j] == 0</code>, or</li>
	<li><code>answer[j] % answer[i] == 0</code></li>
</ul>

<p>If there are multiple solutions, return any of them.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3]
<strong>Output:</strong> [1,2]
<strong>Explanation:</strong> [1,3] is also accepted.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,4,8]
<strong>Output:</strong> [1,2,4,8]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 2 * 10<sup>9</sup></code></li>
	<li>All the integers in <code>nums</code> are <strong>unique</strong>.</li>
</ul>

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        N = len(nums)

        # def can_add(i, j):
        #     a = nums[i]
        #     for b in dp[j]:
        #         if a % b != 0 and b % a != 0:
        #             return False

        #     return True

        nums.sort()
        dp = [[]]*N # [subset]
        ans = []

        for i in range(N):
            dp[i] = [nums[i]]
            for j in range(i):
                if nums[i] % dp[j][-1] == 0: # Check if we can add nums[i] to the subset ending at j
                # No need to loop over all because if a < b < c and b % a == 0 and c % b == 0
                # automatically implies c % a == 0 
                # (If b sized boxes can fit exactly into a c sized space then so can a sized boxes if b= k*a )
                # In other words, if b is a mutiple of a and c is a multiple of b, c is automatically a multiple of a
                    temp = dp[j].copy()
                    temp.append(nums[i])
                    if len(dp[i]) < len(temp): # Subset ending at j and nums[i] is longer than previously longest subset ending at i
                        dp[i] = temp

            if len(dp[i]) > len(ans):
                ans = dp[i]

        return ans
        
        
16825