C++, 6ms: DP, Clean Code & Explanation
C++, 6ms: DP, Simple & Clean Code\nTime: O(n2^n)\nSpace: O(2^n)\n\nSolution:\n\nvector<vector<int>> subsetsWithDup(vector<int>& nums) {\n    sort(nums.begin(), 
C++, 6ms: DP, Simple & Clean Code\n**Time:** O(n*2^n)\n**Space:** O(2^n)\n\n**Solution:**\n```\nvector<vector<int>> subsetsWithDup(vector<int>& nums) {\n    sort(nums.begin(), nums.end());\n\n    vector<vector<int>> r;\n    r.push_back(vector<int>());\n    int prev = 1; \n    \n    for(int i = 0; i < nums.size(); ++i){\n        int n = r.size();\n        int start = (i == 0 || (i > 0 && nums[i] != nums[i-1]) ? 0 : (n - prev));\n        \n        prev = 0;\n        for(int j = start; j < n; ++j){\n            r.push_back(r[j]);\n            r.back().push_back(nums[i]);\n            ++prev;\n        }\n    }\n    \n    return r;\n}\n```\n\n**Explanation:**\n\nI will first show you how the algorithm works with an input array containing no duplication.\n\nFor example, Input: `[1, 2, 3]`\n\nWe first add the empty set to the result.\nThen, for each number in the input, we will concatenate the current number with all the previous results to generate a new set. \n```\nBegin\n1st Round: []\n\n[1, 2, 3]\n ^\n2nd Round: [].push_back(1)\nSets generated: [1]\n\n[1, 2, 3]\n    ^\n3rd Round: [].push_back(2), [1].push_back(2)\nSets generated: [2], [1,2]\n\n[1, 2, 3]\n       ^\n4th Round: [].push_back(3), [1].push_back(3), [2].push_back(3), [1, 2].push_back(3)\nSets generated: [3], [1, 3], [2, 3], [1, 2, 3]\n```\nThen, ` { [ ], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3] } ` is our answer.\n\nNow, let's take a look at an example with duplication.\nFor example, Input: `[1, 2, 2]`\n```\nBegin\n1st Round: []\n\n[1, 2, 2]\n ^\n2nd Round: [].push_back(1)\nSets generated: [1]\n\n[1, 2, 2]\n    ^\n3rd Round: [].push_back(2), [1].push_back(2)\nSets generated: [2], [1, 2]\n\n[1, 2, 2]\n       ^\n4th Round: [].push_back(2), [1].push_back(2), [2].push_back(2), [1, 2].push_back(2)\nSets generated: [2], [1, 2], [2, 2], [1, 2, 2]\n```\n\nYou can observe that the first 2 sets generated in the 4th round are duplication of 3rd round's sets.\nTo fix this problem, we will need to remember how many items were added to our solution which was 2.\nThen, we can avoid using [ ], [1] which were used in the 3rd round to generate those 2 sets.\n```\nBegin\n1st Round: []\n\n[1, 2, 2]\n ^\n2nd Round: [].push_back(1)\nSets generated: [1]\n\n[1, 2, 2]\n    ^\n3rd Round: [].push_back(2), [1].push_back(2)\nSets generated: [2], [1, 2]\n\n[1, 2, 2]\n       ^\n4th Round: [2].push_back(2), [1, 2].push_back(2)\nSets generated: [2, 2], [1, 2, 2]\n```\n\nNow, you should be able to understand this part of the code.\n```\nint start = (i == 0 || (i > 0 && nums[i] != nums[i-1]) ? 0 : (n - prev));\n```\nDon't forget to sort the input array first, otherwise `nums[i] != nums[i-1]` comparison just does not make sense.
['Dynamic Programming', 'C']