Code fully explained Java || Python3 || C++ || C# 🔥😊
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to find the largest divisible subset of a given array of integers. A divisi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to find the largest divisible subset of a given array of integers. A divisible subset is a set of integers where every pair **(nums[i], nums[j])** satisfies **nums[i] % nums[j] == 0** or **nums[j] % nums[i] == 0**. The problem involves dynamic programming to find the length of the largest divisible subset and then reconstructing the subset based on the stored information.\n\n# Approach\n---\n<!-- Describe your approach to solving the problem. -->\n## ***please view comments in code for better understanding***\n\n---\n\n## Sorting:\n\n- The first step is to sort the input array nums. Sorting helps in ensuring that if nums[i] is divisible by nums[j], then nums[j] comes before nums[i].\n## Dynamic Programming:\n\n- Initialize two arrays, a to store the length of the divisible subset ending at index i, and prev to store the previous index in the subset.\n- Iterate through the sorted array and, for each element, iterate through its previous elements to find the longest divisible subset.\n- Update a[i] and prev[i] based on the conditions specified in the code.\n## Reconstruction:\n\n- After computing the lengths and previous indices, reconstruct the largest divisible subset by starting from the index with the maximum length (max and index variables).\n- Add each element to the result list and move to the previous index until reaching the start of the subset.\n\n# Complexity\n- Time complexity:  ***O(n^2)***\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\n```java []\nclass Solution { \n    // Function to find the largest divisible subset\n    public List<Integer> largestDivisibleSubset(int[] nums) {\n        // Arrays to store the length of the subset and the previous index\n        int[] a = new int[nums.length];\n        int[] prev = new int[nums.length];\n        \n        // Sorting the input array\n        Arrays.sort(nums);\n        \n        // Variables to track the maximum length and its corresponding index\n        int max = 0;\n        int index = -1;\n        \n        // Loop through the sorted array\n        for (int i = 0; i < nums.length; i++) {\n            // Initialize the subset length and previous index\n            a[i] = 1;\n            prev[i] = -1;\n            \n            // Iterate through the previous elements to find the longest divisible subset\n            for (int j = i - 1; j >= 0; j--) {\n                if (nums[i] % nums[j] == 0 && a[j] + 1 > a[i]) {\n                    // Update the subset length and previous index\n                    a[i] = a[j] + 1;\n                    prev[i] = j;\n                }\n            }\n            \n            // Update the maximum length and its corresponding index\n            if (a[i] > max) {\n                max = a[i];\n                index = i;\n            }\n        }\n        \n        // Reconstruct the largest divisible subset using the previous indices\n        List<Integer> res = new ArrayList<Integer>();\n        while (index != -1) {\n            res.add(nums[index]);\n            index = prev[index];\n        }\n        \n        // Return the result\n        return res;\n    }\n}\n\n```\n```python3 []\nfrom typing import List\n\nclass Solution:\n    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n        # Sort the input array\n        nums.sort()\n        n = len(nums)\n        # Arrays to store the length of the divisible subset and previous indices\n        a = [1] * n\n        prev = [-1] * n\n        max_len, max_index = 0, -1\n\n        # Dynamic programming to find the length of the largest divisible subset\n        for i in range(n):\n            for j in range(i - 1, -1, -1):\n                if nums[i] % nums[j] == 0 and a[j] + 1 > a[i]:\n                    # Update the subset length and previous index\n                    a[i] = a[j] + 1\n                    prev[i] = j\n\n            # Update the maximum length and its corresponding index\n            if a[i] > max_len:\n                max_len = a[i]\n                max_index = i\n\n        # Reconstruct 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 the result\n        return result\n```\n```c++ []\nclass Solution {\npublic:\n    std::vector<int> largestDivisibleSubset(std::vector<int>& nums) {\n        // Sort the input array\n        std::sort(nums.begin(), nums.end());\n        int n = nums.size();\n        // Arrays to store the length of the divisible subset and previous indices\n        std::vector<int> a(n, 1), prev(n, -1);\n        int max_len = 0, max_index = -1;\n\n        // Dynamic programming to find the length of the largest divisible subset\n        for (int i = 0; i < n; i++) {\n            for (int j = i - 1; j >= 0; j--) {\n                if (nums[i] % nums[j] == 0 && a[j] + 1 > a[i]) {\n                    // Update the subset length and previous index\n                    a[i] = a[j] + 1;\n                    prev[i] = j;\n                }\n            }\n\n            // Update the maximum length and its corresponding index\n            if (a[i] > max_len) {\n                max_len = a[i];\n                max_index = i;\n            }\n        }\n\n        // Reconstruct the largest divisible subset\n        std::vector<int> result;\n        while (max_index != -1) {\n            result.push_back(nums[max_index]);\n            max_index = prev[max_index];\n        }\n\n        // Reverse the result to get the correct order\n        std::reverse(result.begin(), result.end());\n        return result;\n    }\n};\n```\n```c# []\npublic class Solution {\n    public List<int> LargestDivisibleSubset(int[] nums) {\n        // Sort the input array\n        Array.Sort(nums);\n        int n = nums.Length;\n        // Arrays to store the length of the divisible subset and previous indices\n        int[] a = new int[n];\n        int[] prev = new int[n];\n        int max_len = 0, max_index = -1;\n\n        // Dynamic programming to find the length of the largest divisible subset\n        for (int i = 0; i < n; i++) {\n            a[i] = 1;\n            prev[i] = -1;\n\n            for (int j = i - 1; j >= 0; j--) {\n                if (nums[i] % nums[j] == 0 && a[j] + 1 > a[i]) {\n                    // Update the subset length and previous index\n                    a[i] = a[j] + 1;\n                    prev[i] = j;\n                }\n            }\n\n            // Update the maximum length and its corresponding index\n            if (a[i] > max_len) {\n                max_len = a[i];\n                max_index = i;\n            }\n        }\n\n        // Reconstruct the largest divisible subset\n        List<int> result = new List<int>();\n        while (max_index != -1) {\n            result.Add(nums[max_index]);\n            max_index = prev[max_index];\n        }\n\n        // Reverse the result to get the correct order\n        result.Reverse();\n        return result;\n    }\n}\n```\n\n![See-what-sticks.jpg](https://assets.leetcode.com/users/images/61e4ed8c-a0f0-404e-a678-81a0babdb43b_1707456932.8269699.jpeg)\n\n
['Python', 'C++', 'Java', 'Python3', 'C#']