<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>

import math

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        
        # def solve(idx,nums,temp):
        #     if idx >= len(nums):
        #         return temp
            
        #     if len(temp) == 0 or nums[idx]%temp[-1] == 0:
        #         # If this is the case we either take it or we do not
        #         take = solve(idx+1,nums,temp+[nums[idx]])
        #         notTake = solve(idx+1,nums,temp)
        #         return take if len(take) > len(notTake) else notTake
            
        #     return solve(idx+1,nums,temp)
        def solve(idx,nums,temp,ln,dp):
            if idx >= len(nums):
                return []
            if (idx,temp) in dp:
                return dp[(idx,temp)]
            if temp == -1 or nums[idx] % temp == 0:
                take = [nums[idx]]+solve(idx+1,nums,nums[idx],ln+1,dp)
                notTake = solve(idx+1,nums,temp,ln,dp)
                dp[(idx,temp)] = max(take,notTake,key=len)
            else:
                dp[(idx,temp)] = solve(idx+1,nums,temp,ln,dp)
            return dp[(idx,temp)]
            # if ln == 0 or nums[idx] % temp == 0:
            #     take = solve(idx+1,nums,nums[idx],ln+1,dp)
            #     notTake = solve(idx+1,nums,temp,ln,dp)
            #     dp[(idx,temp)] = take if len(take) > len(notTake) else notTake
            # else:
            #     dp[(idx,temp)] = solve(idx+1,nums,temp,ln,dp)
            # return dp[(idx,temp)]
        nums.sort()
        return solve(0,nums,-1,0,{})

            

        
            

64716