✅ [C++] 4 Simple Solutions w/ Detailed Explanation | Optimizations from Brute-Force to DP
We are given an array nums and we need to return the largest subset ans such that when we consider any pair of elements (ans[i], ans[j]), then \n ans[i] % ans[j
We are given an array `nums` and we need to return the largest subset `ans` such that when we consider any pair of elements `(ans[i], ans[j])`, then \n* `ans[i] % ans[j] == 0` or,\n*  `ans[j] % ans[i] == 0`. \n\nThis just means that the larger number should divide the smaller in any pair.\n\n---\n\n\u274C ***Solution - I (Brute-Force)***\n\nLet\'s try to solve this using brute-force approach. For every element, we have the choice to either pick it or not pick it. An element can only be picked when it satisfies the above condition. So, before picking any element, we need to check if either of the above 2 conditions are satisfied or not with each of the element already present in current subset.\n\nBut there\'s an **important observation** that allows us to optimize the above checking process. If the largest number in subset formed till now divides the next element to be chosen, then every other element in the subset will divide it as well (because subset formed till now follows above conditions). For eg. Consider our subset till now is `[1,2,6]` and next element is `12`. If 12 divides largest element of subset - 6, it will divide every other element as well. Try for other examples yourself.\n\nFirstly, for us to use the above observervation, it means the next element should be greater than all existing elements of subset. Then, we can just check if largest element in subset till now divides it completely. If yes, the required condition is satisfied and we can choose this element. \n\nSo, we will sort the `nums` and consider elements to be inserted into subset in increasing order. The process will be as follows -\n* Initially, subset is empty, so any any element can be a valid starting point. Try for each and see which yield largest subset.\n* If subset is not empty, let the last chosen element be `nums[start]`. Then we consider every element at index `next` where `start < next< n` to be chosen next. It will be chosen only if `nums[next] % nums[start] == 0`.\n* We recursively repeat the above process considering `nums[next]` to be previous chosen element and this continues till we reach end of array.\n* At every recursion step, we will return the largest susbet that\'s possible when `nums[start]` was the previous chosen element.\n\n\n```cpp\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(begin(nums), end(nums));\n        vector<int> ans;\n        for(int i = 0; i < size(nums); i++) {         // any element is valid choice for 1st subset member\n            auto res = solve(nums, i);                // try for each & obtain largest subset when nums[i] is starting element\n            if(size(res) > size(ans)) ans = res;      // keep track of largest subset found\n        }\n        return ans;\n    }\n    vector<int> solve(vector<int>& nums, int start) {\n        if(start >= size(nums)) return {};                      // no subset possible when start >= size(nums)\n        vector<int> ans;\n        for(int next = start+1; next < size(nums); next++) {    // try next elements \n            if(nums[next] % nums[start]) continue;              // only those completely divided by nums[start] are valid choice\n            auto res = solve(nums, next);                       // res = largest subset on choosing nums[next]\n            if(size(res) >= size(ans)) ans = res;               // ans = largest subset till now when nums[start] is previous element\n        }\n        ans.push_back(nums[start]);                             // we didnt include nums[start] in ans. Add it as well\n        return ans;                                             // return largest subset starting with num[start]\n    }\n};\n```\n\n\n***Time Complexity :*** **<code>O(N*2<sup>N</sup>) </code>**, where `N` is the number of elements in `nums` array. The recurrence equation for `solve()` can be written as - \n\n```\n                                       \u2193 for making copies of subset array\nT(N) = T(N-1)+T(N-2)+T(N-3)+...+T(1) + N = T(N-1)+T(N-1) + N => T(N) = 2T(N-1) + N\n=> T(N) = 2T(N-1) + N\n```\n\nSolving this using substitution method, we get time complexity as <code>O(2<sup>N</sup>) </code> and we make this call `N` times resulting in total of <code>O(N*2<sup>N</sup>) </code>.\n***Space Complexity :*** **`O(N)`**, required by implicit recursive stack\n\n---\n\n\u2714\uFE0F ***Solution - II (Dynamic Programming - Memoization)***\n\nDrawing out the recursive tree diagram for above solution, we can find that there lots of repeated function calls and redundant calculations. We can avoid these unnecessary calculations by memoizing the results and reusing them in future calls.\n\nHere, we use `dp` to store the largest subset starting with `i`th index element. Once `dp[i]` is calculated, its result can be reused in future calls again instead of recalculating it.\n\n```cpp\nclass Solution {\npublic:\n    unordered_map<int, vector<int>> dp;\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(begin(nums), end(nums));\n        vector<int> ans;\n        for(int i = 0; i < size(nums); i++) {\n            auto res = solve(nums, i);\n            if(size(res) > size(ans)) ans = res;\n        }\n        return ans;\n    }\n    vector<int> solve(vector<int>& nums, int start) {\n        if(start >= size(nums)) return {};\n        if(dp.count(start)) return dp[start];\n        for(int next = start+1; next < size(nums); next++) {\n            if(nums[next] % nums[start]) continue;\n            auto res = solve(nums, next);\n            if(size(res) >= size(dp[start])) dp[start] = res;\n        }\n        dp[start].push_back(nums[start]);\n        return dp[start];\n    }\n};\n```\n\n\n***Time Complexity :*** **<code>O(N<sup>3</sup>) </code>**, \n* For each `i` from `[0...N]`, the largest subset is calculated once. \n* For each calculation, we make `O(N)` iterations from `j = [i...N]`. \n* In each of those iteration, we are making a copy of array of largest subset that we get on picking `j`th element. This size of subset array is bounded by `O(N)` and thus requires additional `O(N)` time. \n* Thus, combining all of this together, the overall time complexity becomes <code>O(N\\*N\\*N) = O(N<sup>3</sup>)</code>\n***Space Complexity :*** **<code>O(N<sup>2</sup>)</code>**, required for memoizing all largest subset results in `dp`.\n\n---\n\n\u2714\uFE0F ***Solution - III (Optimized Dynamic Programming - Memoization)***\n\nIn the above approach, we were memoizing largest subset starting at `i`th index and each time returning a copy of that subset back to top of recursion tree. This leads to higher time as well as space comeplexity. But there exists another approach that we could use here to do it efficiently.\n\nInstead of explicitly generating the largest subset for every index, we can find only the size of **largest subset starting at `i` (given by `dp[i]`) and then try to reconstruct it.** To reconstruct the largest subset, we can keep track of successor element that leads to largest subset starting at index `i`. This reconstruction is similar to the logic used in LIS.\n\n```cpp\nclass Solution {\npublic:\n    vector<int> dp, succ, ans;\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(begin(nums), end(nums));\n\t\t// initially dp[i]=1 since we can always form subset of size=1 starting at i. \n\t\t// succ[i]= \u221E  because we havent found any successors for any subset yet\n        dp.resize(size(nums), 1), succ.resize(size(nums), INT_MAX);\n        for(int i = 0; i < size(nums); i++)  solve(nums, i);\n\t\t// reconstruct starting from index where largest subset starts till the end. succ[i] gives next element after each index\n        for(int i = distance(begin(dp), max_element(begin(dp), end(dp))); i < size(nums); i = succ[i]) \n            ans.push_back(nums[i]);\n        return ans;\n    }\n    int solve(vector<int>& nums, int start) {\n        if(start >= size(nums)) return 0;\n        if(dp[start] != 1) return dp[start];   // initially all dp[i]=1. But if it\'s updated to store largest subset size, just return it.\n        for(int next = start+1; next < size(nums); next++) {\n            if(nums[next] % nums[start]) continue;\n            int size = solve(nums, next);\n            if(dp[start] < size + 1) {   // if choosing subset start at nums[next] gives bigger subset at start, choose it\n                dp[start] = size + 1;    // update dp[i] to store size of largest subset\n                succ[start] = next;      // next element at dp[i] which yields largest subset\n            }\n        }\n        return dp[start];\n    }\n};\n```\n\n***Time Complexity :*** **<code>O(N<sup>2</sup>) </code>**, we require `O(NlogN)` for sorting and then each `dp[i]` is computed once by calling `solve`. `solve` takes `O(N)` and is called `N` times. Thus <code>O(N<sup>2</sup>) </code> for computing the `dp` array. The reconstruction of largest subset is done in `O(N)`. Thus, the total time complexity is <code>O(NlogN + N<sup>2</sup> + N) ~ O(N<sup>2</sup>)</code>\n***Space Complexity :*** **<code>O(N<sup></sup>)</code>**, required for maintaining `dp` and `succ` array\n\n---\n\n\n\n\u2714\uFE0F ***Solution - IV (Optimized Dynamic Programming - Tabulation)***\n\nThe logic is similar to what\'s used in the previous approach with only change being that we are doing it from bottom-up iteratively.\n\nWe keep a `dp` array where `dp[i]` stores the size of **largest subset ending at `i`**. We also keep another array `pred` where `pred[i]` is used to track the predecessors or previous element of subset ending at `i`th index. This will help us in reconstructing the largest subset, just as `succ` did in above approach.\n\nOnce we fill up the dp array, we will start at the index `max_i` having maximum value of `dp[i]` and reconstruct our subset from that. `pred[max_i]` will give us the previous element in largest subset that ended at `max_i`. We can iteratively perform search till `max_i > 0` and push each element into `ans`, and finally return the `ans` array which would be the required largest subset.\n\n```cpp\nclass Solution {\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(begin(nums), end(nums));\n        int n = size(nums), max_i = 0;\n\t\t// initially dp[i]=1 since we can always form subset of size=1 ending at i. \n\t\t// pred[i]=-1 because we havent found any predecessors for any subset yet\n        vector<int> dp(n, 1), pred(n, -1), ans;\n        for(int i = 1; i < n; i++) {          \n            for(int j = 0; j < i; j++)     \n\t\t\t\t// nums[i] should divide nums[j] if it is to be included in its subset (i.e dp[j])\n\t\t\t\t// only include nums[i] in subset ending at j if resultant subset size (dp[j]+1) is larger than already possible (dp[i])\n                if(nums[i] % nums[j] == 0 && dp[i] < dp[j]+1)\n                    dp[i] = dp[j]+1, pred[i] = j;  // jth element will be predecessor to subset ending at ith element\n            if(dp[i] > dp[max_i]) max_i = i;       // keep track of index where largest subset ends\n        }\n\t\t// start with index where largest subset ended. Reconstruct from that point to the start\n        for(; max_i >= 0; max_i = pred[max_i]) \n            ans.push_back(nums[max_i]);\n        return ans;\n    }\n};\n```\n\n***Time Complexity :*** **<code>O(N<sup>2</sup>) </code>**, we require `O(NlogN)` for sorting and then <code>O(N<sup>2</sup>) </code> for computing the `dp` array and then `O(N)` for reconstruction of subset giving total time complexity of <code>O(NlogN + N<sup>2</sup> + N) ~ O(N<sup>2</sup>)</code>\n***Space Complexity :*** **<code>O(N<sup></sup>)</code>**, required for maintaining `dp` and `pred` array\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---
[]