✅☑Beats 99%  Users || [C++/Java/Python/JavaScript] || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n---\n\n# Approaches\n(Also explained in the code)\n\n1. Sort the Numbers: The first step is to sort the input array nums 
# PLEASE UPVOTE IF IT HELPED\n\n---\n![Screenshot 2024-02-09 053555.png](https://assets.leetcode.com/users/images/9324f9ac-1584-438f-88a7-5d009d36bcb4_1707437265.9033418.png)\n\n---\n\n# Approaches\n(Also explained in the code)\n\n1. **Sort the Numbers:** The first step is to sort the input array nums in ascending order. This is done to ensure that we only consider elements that come before the current element during the iteration.\n\n1. **Dynamic Programming (DP) Approach:** We use dynamic programming to find the length of the largest divisible subset ending at each index. We maintain a dp array where dp[i] represents the length of the largest divisible subset ending at index i.\n\n1. **Finding Divisible Subsets:** For each element nums[i], we iterate through all elements before it (nums[j], where j < i) and check if nums[i] is divisible by nums[j]. If it is divisible and adding nums[i] to the subset results in a larger subset, we update the dp[i] value.\n\n1. **Track Maximum Length:** During the DP process, we keep track of the maximum subset length (maxi). This helps us identify the size of the largest divisible subset.\n\n1. **Backtracking to Generate Subset:** Once we have the maximum subset length, we iterate through the dp array from the end to reconstruct the largest divisible subset. We start from the element that corresponds to the maximum subset length and backtrack by adding elements to the result vector (v) while ensuring that each element divides the next element in the subset.\n\n\n# Complexity\n- Time complexity:\n   $$O(n^2)$$\n    \n\n- Space complexity:\n   $$O(n)$$\n    \n\n\n# Code\n```C++ []\n\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        int n=nums.size(), maxi=1, num=-1;\n        vector<int>v;\n        sort(nums.begin(), nums.end());\n        vector<int>dp(n, 1);\n        for(int i=1; i<n; i++){\n            for(int j=0; j<i; j++){\n                if(!(nums[i]%nums[j]) && dp[i]<dp[j]+1){\n                    dp[i]=dp[j]+1;\n                    if(maxi<dp[i]){\n                        maxi=dp[i];\n                    }\n                }\n            }\n        }\n        for(int i=n-1; i>=0; i--){\n            if(maxi==dp[i] && (num==-1 || !(num%nums[i]))){\n                v.push_back(nums[i]);\n                maxi--;\n                num=nums[i];\n            }\n        }\n        return v;\n    }\n};\n\n\n\n\n\n```\n```Java []\nclass Solution {\n    public List<Integer> largestDivisibleSubset(int[] nums) {\n        int n = nums.length;\n        int[] dp = new int[n];\n        Arrays.fill(dp, 1);\n        Arrays.sort(nums);\n        \n        int maxSize = 1, maxIndex = 0;\n        for (int i = 1; i < n; i++) {\n            for (int j = 0; j < i; j++) {\n                if (nums[i] % nums[j] == 0) {\n                    dp[i] = Math.max(dp[i], dp[j] + 1);\n                    if (dp[i] > maxSize) {\n                        maxSize = dp[i];\n                        maxIndex = i;\n                    }\n                }\n            }\n        }\n        \n        List<Integer> result = new ArrayList<>();\n        int num = nums[maxIndex];\n        for (int i = maxIndex; i >= 0; i--) {\n            if (num % nums[i] == 0 && dp[i] == maxSize) {\n                result.add(nums[i]);\n                num = nums[i];\n                maxSize--;\n            }\n        }\n        \n        return result;\n    }\n}\n\n\n```\n```python3 []\nclass Solution:\n    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n        nums.sort()\n        n = len(nums)\n        dp = [1] * n\n        max_size, max_index = 1, 0\n\n        for i in range(1, n):\n            for j in range(i):\n                if nums[i] % nums[j] == 0:\n                    dp[i] = max(dp[i], dp[j] + 1)\n                    if dp[i] > max_size:\n                        max_size = dp[i]\n                        max_index = i\n\n        result = []\n        num = nums[max_index]\n        for i in range(max_index, -1, -1):\n            if num % nums[i] == 0 and dp[i] == max_size:\n                result.append(nums[i])\n                num = nums[i]\n                max_size -= 1\n\n        return result\n\n\n\n```\n```javascript []\nvar largestDivisibleSubset = function(nums) {\n    nums.sort((a, b) => a - b);\n    const n = nums.length;\n    const dp = new Array(n).fill(1);\n    let maxSize = 1, maxIndex = 0;\n\n    for (let i = 1; i < n; i++) {\n        for (let j = 0; j < i; j++) {\n            if (nums[i] % nums[j] === 0) {\n                dp[i] = Math.max(dp[i], dp[j] + 1);\n                if (dp[i] > maxSize) {\n                    maxSize = dp[i];\n                    maxIndex = i;\n                }\n            }\n        }\n    }\n\n    const result = [];\n    let num = nums[maxIndex];\n    for (let i = maxIndex; i >= 0; i--) {\n        if (num % nums[i] === 0 && dp[i] === maxSize) {\n            result.push(nums[i]);\n            num = nums[i];\n            maxSize--;\n        }\n    }\n\n    return result;\n};\n\n\n\n```\n---\n\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['Array', 'Math', 'Dynamic Programming', 'Sorting', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']