Easy Explained🚀➡️In depth Analysis💯➡️[Java/C++/Python3/C#/JavaScript/Rust]
Intuition\n\n## Recursive tree for nums[1 ,2 ,3 ,4]\n\n            [1, 2, 3, 4]\n         /    |      |     \\\n        /      |      |      \\\n     [1]       
# Intuition\n\n## *Recursive tree for nums[1 ,2 ,3 ,4]*\n```\n            [1, 2, 3, 4]\n         /    |      |     \\\n        /      |      |      \\\n     [1]        [2]     [3]     [4]\n    / | \\       / | \\    / |      |\n[1,2] [1,3] [1,3] [1,4] [2,4]   [4]\n   |      |        |        |   \n[1,2,4] [1,2,3,4] [2,4]   [4]\n\n```\n# Approach\n1. **Sort the array:** Sorting the array ensures that smaller numbers come before larger ones, which simplifies the divisibility check process.\n2. **Dynamic Programming Array (`mem`):**\n    - Initialize an array `mem` of the same length as the input array `nums`.\n    - Each element of `mem` will store the size of the largest divisible subset ending at the corresponding index in nums.\n3. **Helper Function (`helper`):**\n    - This function explores all possible subsets of `nums` starting from the `index`.\n    - It uses `prev` to keep track of the previously added element to ensure divisibility.\n    - It updates the `mem` array to store the size of the largest divisible subset ending at each index.\n    - It compares the size of the current subset `curr` with the result `res` and updates `res` if a larger subset is found.\n    - It recursively explores all possible subsets, considering elements from the current index onwards.\n4. **Main Function (`largestDivisibleSubset`):**\n    - Calls the `helper` function to find the largest divisible subset starting from index `0`.\n5. **Returns the result stored in `res`.**\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n*n)$$\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    List<Integer> res;\n    int[] mem;\n    public List<Integer> largestDivisibleSubset(int[] nums) {\n        Arrays.sort(nums);\n        res = new ArrayList<>();\n\n        mem = new int[nums.length];\n        Arrays.fill(mem, -1);\n        helper(nums, 0, new ArrayList<>(), 1);\n        return res;\n    }\n    private void helper(int[] nums, int index, List<Integer> curr, int prev) {\n        if(curr.size() > res.size()) {\n            res = new ArrayList<>(curr);\n        }\n\n        for(int i=index; i<nums.length; i++) {\n            if(curr.size() > mem[i] && nums[i]%prev == 0) {\n                mem[i] = curr.size();\n                curr.add(nums[i]);\n                helper(nums, i+1, curr, nums[i]);\n                curr.remove(curr.size()-1);\n            }\n        }\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    vector<int> res;\n    vector<int> mem;\n\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        res.clear();\n        mem.assign(nums.size(), -1);\n        helper(nums, 0, {}, 1);\n        return res;\n    }\n\n    void helper(vector<int>& nums, int index, vector<int> curr, int prev) {\n        if (curr.size() > res.size()) {\n            res = curr;\n        }\n\n        for (int i = index; i < nums.size(); i++) {\n            if (curr.size() > mem[i] && nums[i] % prev == 0) {\n                mem[i] = curr.size();\n                curr.push_back(nums[i]);\n                helper(nums, i + 1, curr, nums[i]);\n                curr.pop_back();\n            }\n        }\n    }\n};\n```\n```Python3 []\nclass Solution:\n    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n        nums.sort()\n        self.res = []\n        self.mem = [-1] * len(nums)\n        self.helper(nums, 0, [], 1)\n        return self.res\n    \n    def helper(self, nums, index, curr, prev):\n        if len(curr) > len(self.res):\n            self.res = curr[:]\n        \n        for i in range(index, len(nums)):\n            if len(curr) > self.mem[i] and nums[i] % prev == 0:\n                self.mem[i] = len(curr)\n                curr.append(nums[i])\n                self.helper(nums, i + 1, curr, nums[i])\n                curr.pop()\n```\n```C# []\n\npublic class Solution {\n    List<int> res;\n    int[] mem;\n\n    public List<int> LargestDivisibleSubset(int[] nums) {\n        Array.Sort(nums);\n        res = new List<int>();\n        mem = new int[nums.Length];\n        Array.Fill(mem, -1);\n        Helper(nums, 0, new List<int>(), 1);\n        return res;\n    }\n\n    private void Helper(int[] nums, int index, List<int> curr, int prev) {\n        if(curr.Count > res.Count) {\n            res = new List<int>(curr);\n        }\n\n        for(int i = index; i < nums.Length; i++) {\n            if(curr.Count > mem[i] && nums[i] % prev == 0) {\n                mem[i] = curr.Count;\n                curr.Add(nums[i]);\n                Helper(nums, i + 1, curr, nums[i]);\n                curr.RemoveAt(curr.Count - 1);\n            }\n        }\n    }\n}\n```\n```Rust []\npub struct Solution {\n    res: Vec<i32>,\n    mem: Vec<i32>,\n}\n\nimpl Solution {\n    pub fn largest_divisible_subset(nums: Vec<i32>) -> Vec<i32> {\n        let mut sol = Solution { res: vec![], mem: vec![-1; nums.len()] };\n        let mut nums = nums;\n        nums.sort();\n        sol.helper(&nums, 0, &mut vec![], 1);\n        sol.res\n    }\n\n    fn helper(&mut self, nums: &[i32], index: usize, curr: &mut Vec<i32>, prev: i32) {\n        if curr.len() > self.res.len() {\n            self.res = curr.clone();\n        }\n\n        for i in index..nums.len() {\n            if curr.len() > self.mem[i as usize] as usize && nums[i] % prev == 0 {\n                self.mem[i as usize] = curr.len() as i32;\n                curr.push(nums[i]);\n                self.helper(nums, i + 1, curr, nums[i]);\n                curr.pop();\n            }\n        }\n    }\n}\n```\n```JavaScript []\n/**\n * @param {number[]} nums\n * @return {number[]}\n */\nvar largestDivisibleSubset = function(nums) {\n    let res = [];\n    let mem = new Array(nums.length).fill(-1);\n\n    function helper(index, curr, prev) {\n        if (curr.length > res.length) {\n            res = curr.slice();\n        }\n\n        for (let i = index; i < nums.length; i++) {\n            if (curr.length > mem[i] && nums[i] % prev === 0) {\n                mem[i] = curr.length;\n                curr.push(nums[i]);\n                helper(i + 1, curr, nums[i]);\n                curr.pop();\n            }\n        }\n    }\n\n    nums.sort((a, b) => a - b);\n    helper(0, [], 1);\n    return res;\n};\n```\n\n---\n\n\n---\n\n![5c63d377-8ef4-4beb-b09d-0edb07e09a41_1702955205.6568592.png](https://assets.leetcode.com/users/images/962aaaa7-eabf-4d1b-b975-ae0286bd4978_1707508747.8636606.png)\n
['Dynamic Programming', 'Memoization', 'Python', 'C++', 'Java', 'Python3', 'Rust', 'JavaScript', 'C#']