Easy C++ Solution | Beats 96.82% | Recursion | Sorting | DP |
Intuition and Approach\n\n-- We have to find the largest subset of integers from a given array where each pair of elements (a, b) in the subset satisfies the co
# Intuition and Approach\n\n-- We have to find the largest subset of integers from a given array where each pair of elements (a, b) in the subset satisfies the condition **a%b==0** or **b%a==0**.\n\n-- Create a helper function to recursively explore all possible subsets of the input array nums. It takes the current index i, the total number of elements n, the input array nums, a temporary vector temp to store the current subset being considered, and a dynamic programming array dp to memorize the length of the largest divisible subset ending at each index.\n\n-- **Base Case:** If the index i reaches the end of the array nums, the function checks if the current subset temp is larger than the previously recorded result and updates result accordingly.\n\n-- Recursive Calls: The function explores two possibilities\nIf the current subset temp is empty, it adds the current element nums[i] to temp and recursively calls itself with the next index.\n\nIf the current subset temp is not empty and the current element nums[i] is divisible by the last element in temp, it updates the dynamic programming array dp with the length of the subset ending at index i. Then, it adds nums[i] to temp and recursively calls itself with the next index.\n\n-- The $$largestDivisibleSubset$$ function initializes a temporary vector temp and a dynamic programming array dp.\n-- Sort the input array nums in ascending order to simplify the subset generation process. Then, it invokes the $$helper$$ function to explore all possible subsets and returns the largest subset found as the result.\n\n-----------\n\n#### If you find this solution helpful, consider giving it an upvote!\n\n##### Do check out all other solutions posted by me here: https://github.com/adityajamwal02/Leetcode-Community-Solutions\n\n\n-------------\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> result;\n    void helper(int i, int n, vector<int> &nums, vector<int> &temp, vector<int> &dp){\n        if(i==n){\n            if(temp.size()>result.size())\n                result=temp;\n        return;\n        }\n        if(temp.size()==0){\n            temp.push_back(nums[i]);\n            helper(i+1,n,nums,temp,dp);\n            temp.pop_back();\n        }\n        else if((int)temp.size()>dp[i] and nums[i]%temp.back()==0){\n            dp[i]=temp.size();\n            temp.push_back(nums[i]);\n            helper(i+1,n,nums,temp,dp);\n            temp.pop_back();\n        }\n    helper(i+1,n,nums,temp,dp);\n    }\n\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        int n=nums.size();\n        vector<int> temp, dp(n+1,-1);\n        sort(nums.begin(),nums.end());\n        helper(0,n,nums,temp,dp);\n    return result;\n    }\n};\n```
['C++']