368. 最大整除子集

给你一个由无重复正整数组成的集合nums，请你找出并返回其中最大的整除子集answer，子集中每一元素对(answer[i], answer[j])都应当满足：

• answer[i] % answer[j] == 0，或
• answer[j] % answer[i] == 0
  如果存在多个有效解子集，返回其中任何一个均可。

示例 1：

输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例 2：

输入：nums = [1,2,4,8]
输出：[1,2,4,8]

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2 * 10^9
• nums中的所有整数互不相同

1.暴力超时
Python解答：

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        res = []
        nums.sort()
        for n in nums:
            if not res:
                res.append([n])
            else:
                flag = True
                for lis in res[::]:
                    if lis and n % lis[-1] == 0:
                        flag = False
                        temp = copy.deepcopy(lis)
                        temp.append(n)
                        res.append(temp)
                if flag:
                    res.append([n])
        alis = None
        length = 0
        for item in res:
            if len(item) > length:
                alis = item
                length = len(item)
        return alis