48ms solution with subset construction method
One possible solution is to generate all possible subset using bit-mask, and use a set to test the existence of a subset. However, this method may generate dupl
One possible solution is to generate all possible subset using bit-mask, and use a set to test the existence of a subset. However, this method may generate duplicate subsets during the process, and has unsatisfiable time complexity. E.g. for input <1 1 1 1 1 1 1 1 1>, the above method will generate too many duplicate subsets.\n\nI use a subset construction method, whose mechanism is illustrated with an example:\n\ninput: <1 2 2 3 3 3> (assumed to be sorted)\n\ninitialization: empty set <>. ret = {<>}\n\nfor element 1, add it to ret, and we get: <1>. ret = {<> <1>}\n\nfor element 2, add it to ret, and we get: <2> <1 2>; however, notice that we have two elements of 2, hence we further need to add <2 2> to {<> <1>}, and get <2 2> <1 2 2>. ret = {<> <1> <2> <1 2> <2 2> <1 2 2>}\n\nfor element 3, we newly construct the following:              \n<3> <1 3> <2 3> <1 2 3> < 2 2 3> < 1 2 2 3>             \n<3 3> <1 3 3> <2 3 3> <1 2 3 3> <2 2 3 3> <1 2 2 3 3>             \n<3 3 3> <1 3 3 3> < 2 3 3 3> <1 2 3 3 3> <2 2 3 3 3> <1 2 2 3 3 3>                 \nfinally, ret = {<> <1> <2> <1 2> <2 2> <1 2 2>   \n<3> <1 3> <2 3> <1 2 3> < 2 2 3> < 1 2 2 3>   \n<3 3> <1 3 3> <2 3 3> <1 2 3 3> <2 2 3 3> <1 2 2 3 3>   \n<3 3 3> <1 3 3 3> < 2 3 3 3> <1 2 3 3 3> <2 2 3 3 3> <1 2 2 3 3 3>\n}\n\n    class Solution {\n    public:\n        vector<vector<int> > subsetsWithDup(vector<int> &S) {\n            vector<vector<int> > ret;\n            ret.push_back(vector<int>());\n            sort(S.begin(), S.end());\n            for (int i = 0; i < S.size(); ) {\n                int j = i;\n                while (j < S.size() && S[j] == S[i]) j++;\n                int size = ret.size();\n                for (int len = 1; i + len <= j; len++) {\n                    for (int cnt = 0; cnt < size; cnt++) {\n                        vector<int> subset(ret[cnt]);\n                        for (int k = 0; k < len; k++) subset.push_back(S[i]);\n                        ret.push_back(subset);\n                    }\n                }\n                i = j;\n            }\n            return ret;\n        }\n    };
[]