Python | brute force using backtrack | Time complexity O(2^n)
\nclass Solution:\n    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n        \n        \n        # backtrack\n        # time complexity O(2^n
```\nclass Solution:\n    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n        \n        \n        # backtrack\n        # time complexity O(2^n)\n        N = len(nums)\n        \n        # O(nlogn)\n        nums.sort()\n        self.ans = []\n        \n        # use adjusted memoization\n        score = defaultdict(int)\n        \n        # O(2^n)\n        def backtrack(curr, i):\n            if len(curr) > len(self.ans):\n                self.ans = curr[:]\n            for j in range(i+1, N):\n                # if current length + 1 is bigger than previos length\n                # try this number\n                if nums[j] % curr[-1] == 0 and len(curr) + 1 >= score[nums[j]]:\n                    curr.append(nums[j])\n                    score[nums[j]] = len(curr)\n                    backtrack(curr, j)\n                    curr.pop()\n        backtrack([1],-1)\n        \n        # O(n)\n        return self.ans[1:]\n```
[]