largest divisible subset

class (object):
    def largestDivisibleSubset(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        
        if not nums:
            return []
        dp = [1 for _ in range(len(nums))]
        dp_map = {i:[] for i in range(len(nums))}
        nums = sorted(nums)[::-1]
        for i in range(len(nums)):
            dp_map[i] = [nums[i]]
            for j in range(i):
                if nums[j] % nums[i] == 0:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        dp_map[i] = dp_map[j] + [nums[i]]
        
        index = dp.index(max(dp))
        return dp_map[index]
    # backtracking的解法，不过TLE了 
    def largestDivisibleSubset_dfs_method(self, nums):
        nums = sorted(nums)
        self.m = [False for _ in range(len(nums))]
        self.max_length = 0
        self.ret = []
        for i in range(len(nums)):
            if m[i]:
                continue
            cur = [nums[i]]
            pos = i + 1
            self.dfs(nums, pos, cur)
        
        return self.ret
    
    def dfs(self, nums, pos, cur):
        # 从pos开始依次找到所有能加入到cur的数
        if len(cur) > self.max_length:
            self.max_length = len(cur)
            self.ret = cur[:]
        for i in range(pos, len(nums)):
            if nums[i] % cur[-1] == 0:
                cur.append(nums[i])
                self.dfs(nums, i+1, cur)
                cur.pop()