[C++]✅4 Easy Solutions | Brute Force | Recursion | Memoization | Tabulation
Approach 1 : Brute Force\n Describe your approach to solving the problem. \nCompute all subsets and return the required one.\n\n# Complexity\n- Time complexity:
# Approach 1 : Brute Force\n<!-- Describe your approach to solving the problem. -->\nCompute all subsets and return the required one.\n\n# Complexity\n- Time complexity: $$O(n*log(n)*2^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 1 : <span style="color:red">Run Time Error</span>\n``` C++ []\nclass Solution {\nprivate:\n    bool isDivisibleSubset(vector<int> nums){\n        sort(nums.begin(), nums.end());\n        for(int i=nums.size()-1;i>=1;--i){\n            if(nums[i] % nums[i-1]!=0){\n                return 0;\n            }\n        }\n        return 1;\n    }\n\n    vector<vector<int>> computeSubsets(vector<int> &nums){\n        vector<vector<int>> subsets;\n        int N = nums.size();\n        for(int i=0; i<(1<<N); ++i){\n            vector<int> v;\n            int j = 0;\n            while((1<<j) <= i){    \n                if(((1<<j) & i) > 0){\n                    v.push_back(nums[j]);\n                }\n                j++;\n            }\n            if(v.size() > 0) subsets.push_back(v);\n        }\n        return subsets;\n    }\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        vector<vector<int>> Subsets = computeSubsets(nums);\n        vector<int> largest_subset;\n        for(vector<int> subset : Subsets){ \n            if(isDivisibleSubset(subset) and largest_subset.size() < subset.size()){\n                largest_subset = subset;\n            }\n        }\n        return largest_subset;\n    }\n};\n```\n\n---\n\n# Approach 2 : Recursion\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(2^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 2 : <span style="color:red">Time Limit Exceeded</span>\n``` C++ []\nclass Solution {\nprivate:\n    void solve(int index, int prev, vector<int>&nums, vector<int>&curr,  vector<int>&ans){\n        if(index >= nums.size()){\n            if(curr.size() > ans.size()){\n                ans = curr;\n            }\n            return;\n        }\n\n        // take\n        if(prev == -1 || nums[index] % prev == 0){\n            curr.push_back(nums[index]);\n            solve(index+1, nums[index], nums, curr, ans);\n            curr.pop_back();    // backtrack\n        }\n\n        // not take\n        solve(index+1, prev, nums, curr, ans);\n    }\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n\n        int prev = -1;  // last element divisible by subset elements\n        vector<int>ans, curr;\n        solve(0, prev, nums, curr, ans);\n\n        return ans;\n    }\n};\n```\n---\n\n# Approach 3 : Memoization\n<!-- Describe your approach to solving the problem. -->\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^3)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n### It has passed some big testcase which recursion gave TLE.\n\n# Code 3 : <span style="color:red">Wrong Answer</span> (IDK why?)\n``` C++ []\nclass Solution {\nprivate:\n    unordered_map<string, vector<int>> memo;\n\n    void solve(int index, int prev, vector<int>& nums, vector<int>& curr, vector<int>& ans) {\n        if (index >= nums.size()) {\n            if (curr.size() > ans.size()) {\n                ans = curr;\n            }\n            return;\n        }\n\n        string key = to_string(index) + "|" + to_string(prev);\n        if (memo.find(key) != memo.end()) {\n            if (memo[key].size() > ans.size()) {\n                ans = memo[key];\n            }\n            return;\n        }\n\n        // Take\n        if (prev == -1 || nums[index] % prev == 0) {\n            curr.push_back(nums[index]);\n            solve(index + 1, nums[index], nums, curr, ans);\n            curr.pop_back(); // Backtrack\n        }\n\n        // Not take\n        solve(index + 1, prev, nums, curr, ans);\n\n        // Memoize the result\n        memo[key] = ans;\n    }\n\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        memo.clear();\n        sort(nums.begin(), nums.end());\n\n        int prev = -1;  // last element divisible by subset elements\n        vector<int>ans, curr;\n        solve(0, prev, nums, curr, ans);\n\n        return ans;\n    }\n};\n```\n---\n\n# Approach 4 : Tabulation\n<!-- Describe your approach to solving the problem. -->\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 4 : <span style="color:green">Accepted</span>\n``` C++ []\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n\n        int n = nums.size(), lastIdx = 0, maxLen = 1;\n        vector<int> dp(n, 1), prev(n, -1);\n\n        for(int i = 0; i < nums.size(); i++) {\n            for(int j = 0; j < i; j++) {\n                if(nums[i]%nums[j] == 0) {\n                    if(dp[i] < dp[j]+1) {\n                        dp[i] = dp[j]+1;\n                        prev[i] = j;\n                    }\n\n                    if(dp[i] > maxLen){\n                        maxLen = dp[i];\n                        lastIdx = i;\n                    }\n                }\n            }\n        }\n\n        vector<int> ans;\n        while(lastIdx != -1) {\n            ans.push_back(nums[lastIdx]);\n            lastIdx = prev[lastIdx];\n        }\n        \n        return ans;\n    }\n};\n```
['Array', 'Math', 'Dynamic Programming', 'Recursion', 'Memoization', 'Sorting', 'C++']