✅☑ALL || Easy Understood Solution with optimized space || 3 Approaches🔥
\n\n# Explanation:\n  - Sort the array for efficient exploration.\n  - Use memoization to store and retrieve already calculated results.\n  - The recursive func
![111.PNG](https://assets.leetcode.com/users/images/fcaa9602-15d4-4ba2-a3b7-f0f6175ceca3_1707505865.9286792.png)\n\n# Explanation:\n  - Sort the array for efficient exploration.\n  - Use memoization to store and retrieve already calculated results.\n  - The recursive function dfs(i, prev) explores two choices: not taking the current element and taking it.\n  - The base case is when the end of the array is reached.\n  - The memoized result is returned if available.\n  - Explore taking the current element only if it\'s divisible by the previous element.\n  - Return the larger subset between not taking and taking the current element.\n  - Memoize the result and return it.\n  - Start the recursive DFS from the beginning with a dummy \'prev\' set to 1.\n\n# Complexity\n- Time complexity: O(n^2), where n is the length of the input list nums.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code 1\n```\nclass Solution:\n    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n        nums.sort()  # Sort the array for better exploration\n        memo = {}    # Memoization to store calculated results\n\n        def dfs(i, prev):\n            if i == len(nums):  # Base case: reached the end of the array\n                return []\n\n            if (i, prev) in memo:  # Return memoized result if available\n                return memo[(i, prev)]\n\n            res = dfs(i + 1, prev)  # Explore not taking the current element\n\n            if prev == 1 or nums[i] % prev == 0:  # Explore taking the current element\n                tmp = [nums[i]] + dfs(i + 1, nums[i])\n                if len(tmp) > len(res):\n                    res = tmp  # Update result if the current subset is larger\n\n            memo[(i, prev)] = res  # Memoize the result\n            return res\n\n        return dfs(0, 1)  # Start the recursive DFS from the beginning with a dummy \'prev\'\n\n```\n# Code 2 \uD83D\uDD25\n# Explanation:\n  - Base Case Handling:\n    - If the input list nums is empty, return an empty list since there is no divisible subset.\n  - Initialization:\n    - Get the length of the input list nums and sort it. Sorting is crucial for the divisibility condition to work efficiently.\n  - Dynamic Programming Arrays:\n    - Create two arrays, dp and prev_index.\n    - dp: Represents the length of the largest divisible subset ending at index i.\n    - prev_index: Keeps track of the previous index that contributes to the largest divisible subset ending at index i.\n  - Dynamic Programming Loop:\n    - Iterate over the indices i from 1 to n-1 (excluding the first index).\n    - For each index i, iterate over the indices j from 0 to i-1.\n    - Check if nums[i] is divisible by nums[j] and if the current subset length at index i is less than dp[j] + 1.\n    - If the conditions are met, update dp[i] and prev_index[i].\n  - Finding Maximum Length:\n    - Find the index (max_index) of the maximum value in the dp array.\n  - Reconstructing Subset:\n    - Initialize an empty list result.\n    - While max_index is not -1:\n      - Append the element at index max_index from the sorted nums list to the result.\n      - Update max_index to its previous index stored in prev_index.\n  - Returning Result:\n    - Return the reversed result to get the correct order of the largest divisible subset. \n\n``` Python []\nclass Solution:\n    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n        if not nums:\n            return []\n\n        n = len(nums)\n        nums.sort()  # Sorting is necessary for the divisibility condition to work\n        dp = [1] * n\n        prev_index = [-1] * n  # To reconstruct the subset later\n\n        for i in range(1, n):\n            for j in range(i):\n                if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:\n                    dp[i] = dp[j] + 1\n                    prev_index[i] = j\n\n        # Find the index of the maximum value in dp\n        max_index = dp.index(max(dp))\n        \n        # Reconstruct the subset\n        result = []\n        while max_index != -1:\n            result.append(nums[max_index])\n            max_index = prev_index[max_index]\n\n        return result[::-1]  # Reverse the result to get the correct order\n```\n``` Java []\nimport java.util.ArrayList;\nimport java.util.Arrays;\nimport java.util.List;\n\npublic class Solution {\n    public List<Integer> largestDivisibleSubset(int[] nums) {\n        if (nums == null || nums.length == 0) {\n            return new ArrayList<>();\n        }\n\n        int n = nums.length;\n        Arrays.sort(nums);\n\n        int[] dp = new int[n];\n        int[] prevIndex = new int[n];\n        Arrays.fill(dp, 1);\n        Arrays.fill(prevIndex, -1);\n\n        for (int i = 1; i < n; i++) {\n            for (int j = 0; j < i; j++) {\n                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {\n                    dp[i] = dp[j] + 1;\n                    prevIndex[i] = j;\n                }\n            }\n        }\n\n        int maxIndex = 0;\n        for (int i = 1; i < n; i++) {\n            if (dp[i] > dp[maxIndex]) {\n                maxIndex = i;\n            }\n        }\n\n        List<Integer> result = new ArrayList<>();\n        while (maxIndex != -1) {\n            result.add(nums[maxIndex]);\n            maxIndex = prevIndex[maxIndex];\n        }\n\n        return result;\n    }\n}\n```\n``` C++ []\n#include <iostream>\n#include <vector>\n#include <algorithm>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        if (nums.empty()) {\n            return {};\n        }\n\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n\n        vector<int> dp(n, 1);\n        vector<int> prevIndex(n, -1);\n\n        for (int i = 1; i < n; i++) {\n            for (int j = 0; j < i; j++) {\n                if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {\n                    dp[i] = dp[j] + 1;\n                    prevIndex[i] = j;\n                }\n            }\n        }\n\n        int maxIndex = max_element(dp.begin(), dp.end()) - dp.begin();\n\n        vector<int> result;\n        while (maxIndex != -1) {\n            result.push_back(nums[maxIndex]);\n            maxIndex = prevIndex[maxIndex];\n        }\n\n        reverse(result.begin(), result.end());\n        return result;\n    }\n};\n```\n``` JavaScript []\n/**\n * @param {number[]} nums\n * @return {number[]}\n */\nvar largestDivisibleSubset = function(nums) {\n    if (!nums || nums.length === 0) {\n        return [];\n    }\n\n    const n = nums.length;\n    nums.sort((a, b) => a - b);\n\n    const dp = new Array(n).fill(1);\n    const prevIndex = new Array(n).fill(-1);\n\n    for (let i = 1; i < n; i++) {\n        for (let j = 0; j < i; j++) {\n            if (nums[i] % nums[j] === 0 && dp[i] < dp[j] + 1) {\n                dp[i] = dp[j] + 1;\n                prevIndex[i] = j;\n            }\n        }\n    }\n\n    let maxIndex = dp.indexOf(Math.max(...dp));\n\n    const result = [];\n    while (maxIndex !== -1) {\n        result.push(nums[maxIndex]);\n        maxIndex = prevIndex[maxIndex];\n    }\n\n    return result.reverse();\n};\n```\n# Code 3 \uD83D\uDD25\n# Explanation:\n  - Memoization Approach (largestDivisibleSubsetMemoization):\n    - Recursively explores subsets with memoization to avoid redundant computations.\n    - Returns the length of the largest divisible subset and its starting element.\n    - Uses caching (@cache) to store and retrieve calculated results.\n  - Dynamic Programming Approach (largestDivisibleSubset):\n    - Iterates through sorted nums and updates subsets dynamically.\n    - subsets stores the largest divisible subset ending at each number.\n    - Uses dynamic programming to efficiently build valid subsets.\n    - Returns the largest divisible subset found.\n```\nclass Solution:\n    def largestDivisibleSubsetMemoization(self, nums: List[int]) -> List[int]:\n        nums.sort()\n\n        # Recursive function with memoization\n        @cache\n        def dfs(i, prev_index):\n            if i == len(nums):\n                return 0, -1\n\n            length1, ele1 = dfs(i+1, prev_index)\n            length2, ele2 = -1, -1\n\n            # Check if the current number can be added to the subset\n            if nums[i] % (nums[prev_index] if prev_index != -1 else 1) == 0:\n                length2, ele2 = dfs(i+1, i)\n                length2 += 1\n            \n            # Choose the longer subset and update the ladder_map\n            if length2 > length1:\n                ladder_map[nums[i]] = ele2\n                return length2, nums[i]\n            else:\n                return length1, ele1\n\n        _, starting_ele = dfs(0, -1)\n        res = []\n\n        # Reconstruct the largest divisible subset\n        while starting_ele != -1:\n            res.append(starting_ele)\n            starting_ele = ladder_map[starting_ele]\n        \n        return res\n    \n    def largestDivisibleSubset(self, nums):\n        # The container that holds all intermediate solutions.\n        # key: the largest element in a valid subset.\n        subsets = {-1: set()}\n        \n        # Iterate through sorted nums and update subsets dynamically\n        for num in sorted(nums):\n            subsets[num] = max([subsets[k] for k in subsets if num % k == 0], key=len) | {num}\n        \n        # Return the largest divisible subset found\n        return list(max(subsets.values(), key=len))\n```\n![leetcode up1.png](https://assets.leetcode.com/users/images/a408fa14-99a7-41a6-9ee2-fd0ef63cdb38_1707507190.7196236.jpeg)\n\n\n
['Array', 'Hash Table', 'Math', 'Dynamic Programming', 'Depth-First Search', 'Recursion', 'C++', 'Java', 'Python3', 'JavaScript']