c++ O(N^2) creative solution with explanation, using graph
We essentially build a divisibility based poset with nums. This means we consider a >> b if a % b == 0 (if b divides a). ( >> just means "greater than", but l n
We essentially build a divisibility based [poset](https://en.wikipedia.org/wiki/Partially_ordered_set) with nums. This means we consider a >> b if a % b == 0 (if b divides a). ( >> just means "greater than", but l needed to differentiate between this new ordering at the standard ordering, which will be denoted by >). \nFor each new num a we add the poset, we insert it as a "child" to any node b such that a >> b and **that a is not >> any of b\'s children**. Note that this structure is not a tree, since a node can have more than 1 parent. Also note that it is easiest to build it correctly if we go in order from smallest to largest element, since if a is >> b, a is also > b.\n\n1. First we insert 1, 2, 3. 1 is the root. Both 2 and 3 are divisible by 1, so they are "children" of 1. \n![image](https://assets.leetcode.com/users/apluscs/image_1586357429.png)\n2. Next we insert 4 and 5. 4 is divisible by 1, yes, but it is also divisible by 2, which is a child of 1. That means we should not insert it as a child of 1 but actually as a child of 2. \n![image](https://assets.leetcode.com/users/apluscs/image_1586357647.png)\n3. Finally, let\'s insert the rest of the elements. 6 has two parents, since it can be divided by both 2 and 3. Same goes for 10 and 12.\n![image](https://assets.leetcode.com/users/apluscs/image_1586357935.png)\n\nNow once this diagram is built, how can it be used to answer the problem? Notice the problem basically asks for one of the longest "lines" from root to any leaf. In this example, we have potential answers [1,2,4,8], [1,2,4,12], [1,2,6,12], [1,3,6,12]. This makes sense, since whenever you add an element to the "end" of a preexisting line, you know it is divisible by every element in that line.\n\nMy code:\n\n```\nclass Solution {\npublic:\n    struct Node{\n        unordered_set<Node*> kids;\n        int val;\n        Node(int val) : val(val){}\n    };\n    \n    vector<int> res;\n    vector<int> largestDivisibleSubset(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        res.clear();\n        if(nums.empty()) return res;\n        Node* root = new Node(1);   // \'assume\' we have a 1 in nums\n        for(int num : nums){\n            Node* curr = new Node(num);\n            update(root, curr);\n        }\n        vector<int> subset;\n        dfs(root, subset);\n        if(nums[0] == 1) return res;    // assumption is valid\n        for(int i = 0; i != res.size(); ++i){    // else we know nums doesn\'t have a 1\n            if(res[i] == 1){\n                res.erase(res.begin() + i); // erase from answer\n                break;\n            } \n        }\n        return res;\n    }\n    \n    void dfs(Node* root, vector<int>& subset){\n        subset.push_back(root->val);\n        if(root->kids.empty()){ // reached the end of the line\n            if(subset.size() > res.size()) res = subset;    // compare line sizes\n        }\n        for(auto kid : root->kids)\n            dfs(kid, subset);\n        subset.pop_back();\n    }\n    \n    bool update(Node* root, Node* curr){    // update the poset\n        int num = curr->val, rum = root->val;\n        if(num % rum != 0 || num == rum) return false;    // cannot be a member of root\'s descendants\n        bool found = false; \n        for(auto kid : root->kids)\n            if(update(kid, curr))\n                found = true;   // curr is divisible by at least one of root\'s kids\n        if(!found) root->kids.insert(curr); // only insert if root is the \'last\' node that divides curr\n            \n        return true;\n    }\n};\n```\n\nTime complexity: N log N from sorting, N^2 worst case for updating :/ = O(N^2)
[]