6ms C++ beats 100% w/ explanations
Solution #1 (TLE)\nThis solution builds upon the naive approach of building up a solution by either adding an element to the solution (if it passes the divisibi
**Solution #1 (TLE)**\nThis solution builds upon the naive approach of building up a solution by either adding an element to the solution (if it passes the divisibility check) or by skipping the value as all nums are iterated over. Nums is first sorted so that it is easier to test if a new (larger) num satisfies the divisibility check of the current solution by only checking the last element of the solution (others, like @StefanPochmann, have talked about this). Speed is O(2^n), and Space is O(n).\n```\nclass Solution {\n    int bSz=0, sPos=0, nSz;\n    vector<int> nums, sol, best=vector<int>(0);\n    \n    int passes(int v, int i) {\n        return ( (sPos==0) || ((v%sol[sPos-1])==0) );\n    }\n    void rec(int i) {\n        for ( ; i<nSz; ++i ) {\n            if ( passes(nums[i],i) ) {\n                sol[sPos++]=nums[i];\n                rec(i+1);   // w/ num[i] in solution\n                --sPos;\n            }               // else, w/o num[i] in solution\n        }\n        if ( bSz < sPos ) {\n            bSz = sPos;     // store best\n            best = vector<int>(sol.begin(), sol.begin()+sPos);\n        }\n    }\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& numsOrig) {\n        if ( (nSz=numsOrig.size())<=1 ) return numsOrig; \n        nums = numsOrig;\n        sol = vector<int>(nSz);\n        //\n        sort (nums.begin(), nums.end());\n        //\n        rec(0);\n        return best;\n    }\n};\n```\n**Solution #2 (Accepted 149ms)**\nLike Dijkstra's shortest path algorithm, it can be observed that a num should only be considered if it contributes to a better solution (in this case a longer subset). Therefore the distance of a num contributing to any partial solution can be recorded in a 'furthest' vector (where it is found in the solution), of size n, and only be considered again if it has a further solution position. \n```// don't consider the num 32 in a solution of [1,32,...] when a better solution [1,2,4,32,...] has already been found```\nSomeone can correct me if I am wrong, but I believe the Speed is O(n^2) and the Space is still O(n). The reason it is no longer O(2^n) is because the the outer loop runs in O(n) while the inner recursive loop now only expands ~once per new divisible num, also O(n). In other words, the recursive portion is like a DFS that walks the remaining nodes once; then, later attempts to visit the same node are rejected for not having a further solution position.\n```\nclass Solution {\n    int bSz=0, sPos=0, nSz;\n    vector<int> nums, sol, furthest, best=vector<int>(0);\n    \n    int passes(int v, int i) {\n        if ( sPos==0 ) return 1;\n        if ( (sPos>furthest[i]) && ((v%sol[sPos-1])==0) ) {\n            furthest[i]=sPos;\n            return 1;       // mark the position\n        }\n        return 0;\n    }\n    void rec(int i) {\n        for ( ; i<nSz; ++i ) {\n            if ( passes(nums[i],i) ) {\n                sol[sPos++]=nums[i];\n                rec(i+1);   // w/ num[i] in solution\n                --sPos;\n            }               // else, w/o num[i] in solution\n        }\n        if ( bSz < sPos ) {\n            bSz = sPos;     // store best\n            best = vector<int>(sol.begin(), sol.begin()+sPos);\n        }\n    }\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& numsOrig) {\n        if ( (nSz=numsOrig.size())<=1 ) return numsOrig; \n        nums = numsOrig;\n        sol = vector<int>(nSz);\n        furthest = vector<int>(nSz,0);\n        //\n        sort (nums.begin(), nums.end());\n        //\n        rec(0);\n        return best;\n    }\n};\n```\n**Solution #3 (Accepted 6ms)**\nAdditional pruning can be added for early rejection of numbers that will not contribute to a better solution than what has already been found, with the below check:\n```// given input [1...1000] and a current best solution of [1,2,4,8...512], don't proceed with a solution like [1,3,99] or [1,400] because the optimal way to expand these solutions would be to multiply the last number by 2 repeatedly, but a larger best-subset would require a final number > 1000. ```\nSo a check is added to our iterative loop to see if there remains a large enough num to satisfy this constraint with: largest > num * 2^(difference in solution size to the best known solution size). This check requires O(1) additional complexity leaving the Speed at O(n^2) and the Space O(n).\n```\nclass Solution {\n    int bSz=0, sPos=0, nSz, largest;\n    vector<int> nums, sol, furthest, best=vector<int>(0);\n    \n    int passes(int v, int i) {\n        if ( sPos==0 ) return 1;\n        if ( (sPos>furthest[i]) && ((v%sol[sPos-1])==0) ) {\n            furthest[i]=sPos;\n            return 1;       // mark the position\n        }\n        return 0;\n    }\n    void rec(int i) {\n        for ( ; i<nSz; ++i ) {\n            if ( bSz>sPos && ((((long)1)<<(bSz-sPos))*nums[i])>largest ) break;\n            if ( passes(nums[i],i) ) {\n                sol[sPos++]=nums[i];\n                rec(i+1);   // w/ num[i] in solution\n                --sPos;\n            }               // else, w/o num[i] in solution\n        }\n        if ( bSz < sPos ) {\n            bSz = sPos;     // store best\n            best = vector<int>(sol.begin(), sol.begin()+sPos);\n        }\n    }\npublic:\n    vector<int> largestDivisibleSubset(vector<int>& numsOrig) {\n        if ( (nSz=numsOrig.size())<=1 ) return numsOrig; \n        nums = numsOrig;\n        sol = vector<int>(nSz);\n        furthest = vector<int>(nSz,0);\n        //\n        sort (nums.begin(), nums.end());\n        largest = nums.back();\n        //\n        rec(0);\n        return best;\n    }\n};\n```
[]