368: Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThis is a dynamic programming solution to find the largest divisible subs
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThis is a dynamic programming solution to find the largest divisible subset of a set of distinct positive integers.\n\nThe basic idea is to sort the input array so that we can process it in increasing order. We initialize two arrays: dp and prev. dp[i] stores the size of the largest divisible subset that ends with nums[i], while prev[i] stores the index of the previous element in the largest divisible subset that ends with nums[i].\n\nWe then iterate over the input array, and for each element nums[i], we check all previous elements nums[j] (j < i). If nums[i] is divisible by nums[j], and the size of the largest divisible subset that ends with nums[j] plus one is greater than the current size of dp[i], we update dp[i] and prev[i]. At the end of this process, we have computed the size of the largest divisible subset, which is stored in max_size, and the index of the last element in the largest divisible subset, which is stored in max_index.\n\nWe then use the prev array to backtrack from max_index to the first element in the largest divisible subset, appending each element to a result list. Finally, we return the result list in reverse order (since we built the list backwards during the backtracking process).\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n  def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n    if not nums:\n        return []\n    # Sort the input array\n    nums.sort()\n    \n    # Initialize a dynamic programming table\n    # dp[i] stores the size of the largest divisible subset that ends with nums[i]\n    dp = [1] * len(nums)\n    \n    # Initialize a backtracking table\n    # prev[i] stores the index of the previous element in the largest divisible subset that ends with nums[i]\n    prev = [-1] * len(nums)\n    \n    # Find the largest divisible subset and its size\n    max_size = 1\n    max_index = 0\n    for i in range(1, len(nums)):\n        for j in range(i):\n            if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:\n                dp[i] = dp[j] + 1\n                prev[i] = j\n        if dp[i] > max_size:\n            max_size = dp[i]\n            max_index = i\n    \n    # Backtrack to find the largest divisible subset\n    result = []\n    while max_index != -1:\n        result.append(nums[max_index])\n        max_index = prev[max_index]\n    \n    return result[::-1]\n\n```
['Array', 'Math', 'Dynamic Programming', 'Python', 'Python3']