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

        parents = [None] * N
        for i in range(N):
            best = (None, 0)
            for j in range(i):
                if nums[j] % nums[i] != 0:
                    continue
                if parents[j][2] + 1 > best[1]:
                    best = (j, parents[j][2] + 1)
            parents[i] = (i, best[0], best[1])

        longest = max(parents, key=lambda p: p[2])

        ans = []
        while True:
            ans.append(nums[longest[0]])
            if longest[1] is None:
                break
            longest = parents[longest[1]]
        return ans