<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]:
        nums.sort()
        cache = {}
        def dfs(i,prev):
            if (i,prev) in cache:
                return cache[(i,prev)]
            if i == len(nums):
                return []
            include = []
            if not nums[i] % prev:
                # can include number
                include = [nums[i]]+ dfs(i+1,nums[i])

            skip = dfs(i+1,prev)
            res =include if len(include)> len(skip) else skip
        
            cache[(i,prev)] = res

            return res
        return dfs(0,1)

    def largestDivisibleSubsetMine_Works_slow(self, nums: List[int]) -> List[int]:

        if len(nums) <2:
            return nums

        nums.sort()
        dp = [[] for _ in range(len(nums))]
        if nums[0] == 1:
            has1 = True
            nums = nums[1:]
        else:
            has1 = False
        dp[0] = [nums[0]]
        for i in range(1,len(nums)):
                for j in range(len(dp)):
                    numberToCopy = None
                    if j < i:
                        if not nums[i] % dp[j][-1] and len(dp[j]) > len(dp[i]):
                            dp[i] = dp[j][:]
                    else:
                        dp[i].append(nums[i])
                        break
        res = []
        for candidate in dp:
            if len(candidate) > len(res):
                res = candidate
        if has1:
            res.append(1)
        return res





    def largestDivisibleSubsetDoesNotWork(self, nums: List[int]) -> List[int]:

        oddset = []
        evenset = []
        primeset = []

        has1 = False
        for n in nums:
            if n == 1:
                has1 = True
            else:
                if not n % 2:
                    evenset.append(n)
                elif not n % 3:
                    oddset.append(n)
                elif not primeset:
                    primeset.append(n)

        res =  evenset if len(evenset) >= len(oddset) else oddset
        res =  res if len(res) >= len(primeset) else primeset
        if has1:
            res.append(1)
        return res
48753