C++ Solution with Explanations
The key concept here is:\n  Given a set of integers that satisfies the property that each pair of integers inside the set are mutually divisible, for a new inte
The key concept here is:\n  Given a set of integers that satisfies the property that each pair of integers inside the set are mutually divisible, for a new integer S, S can be placed into the set as long as it can divide the smallest number of the set or is divisible by the largest number of the set.\n\t\nFor example, let's say we have a set P = { 4, 8, 16 }, P satisfies the divisible condition. Now consider a new number 2, it can divide the smallest number 4, so it can be placed into the set; similarly, 32 can be divided by 16, the biggest number in P, it can also placed into P.\n\nNext, let's define:\n\n**EDIT: For clarification, the following definitions try to enlarge candidate solutions by appending a larger element at the end of each potential set, while my implementation below is prefixing a smaller element at the front of a set. Conceptually they are equivalent but by adding smaller elements at the front saves the trouble for keeping the correct increasing order for the final answer. Please refer to comments in code for more details.**\n\nFor an increasingly sorted array of integers a[1 .. n]\n\nT[n] = the length of the largest divisible subset whose largest number is a[n]\n\nT[n+1] = max{ 1 + T[i] if a[n+1] mod a[i] == 0 else 1 }\n\nNow, deducting T[n] becomes straight forward with a DP trick. For the final result we will need to maintain a backtrace array for the answer.\n\nImplementation in C++:\n\n    class Solution {\n    public:\n        vector<int> largestDivisibleSubset(vector<int>& nums) {\n            sort(nums.begin(), nums.end());\n            \n            vector<int> T(nums.size(), 0);\n            vector<int> parent(nums.size(), 0);\n            \n            int m = 0;\n            int mi = 0;\n            \n            // for(int i = 0; i < nums.size(); ++i) // if extending by larger elements\n            for(int i = nums.size() - 1; i >= 0; --i) // iterate from end to start since it's easier to track the answer index\n            {\n                // for(int j = i; j >=0; --j) // if extending by larger elements\n                for(int j = i; j < nums.size(); ++j)\n                {\n                    // if(nums[i] % nums[j] == 0 && T[i] < 1 + T[j]) // if extending by larger elements\n                    // check every a[j] that is larger than a[i]\n                    if(nums[j] % nums[i] == 0 && T[i] < 1 + T[j])\n                    {\n                        // if a[j] mod a[i] == 0, it means T[j] can form a larger subset by putting a[i] into T[j]\n                        T[i] = 1 + T[j];\n                        parent[i] = j;\n                        \n                        if(T[i] > m)\n                        {\n                            m = T[i];\n                            mi = i;\n                        }\n                    }\n                }\n            }\n            \n            vector<int> ret;\n            \n            for(int i = 0; i < m; ++i)\n            {\n                ret.push_back(nums[mi]);\n                mi = parent[mi];\n            }\n\n            // sort(ret.begin(), ret.end()); // if we go by extending larger ends, the largest "answer" element will come first since the candidate element we observe will become larger and larger as i increases in the outermost "for" loop above.\n           // alternatively, we can sort nums in decreasing order obviously. \n            \n            return ret;\n        }\n    };
['Dynamic Programming']