Python solution
Use a dictionary to keep track of the number of appearances of each number. One can then easily construct the power set of nums based on this dictionary.\n\nE.g
Use a dictionary to keep track of the number of appearances of each number. One can then easily construct the power set of `nums` based on this dictionary.\n\nE.g., `nums = [1,1,2,2,2,4,4,5]`. In this case `dic = {1:2, 2:3, 4:2, 5:1}`. We intialize `res = [[]]`, and build the solution iteratively as we loop over the dictionary. We first reach `key, val = 1, 2`. The power set of `[1,1]` is `res = [[], [1], [1,1]]`. Then we reach `key, val = 2, 3`. The power set of `[1,1,2,2,2]` is obtained by appending either `0`, `1`, `2`, or `3` 2\'s to all elements in `res`. After which we get `res = [[], [1], [1,1], [2], [1,2], [1,1,2],[2,2], [1,2,2], [1,1,2,2],[2,2,2], [1,2,2,2], [1,1,2,2,2]]`. After we loop over `dic`, `res` will be the power set of `nums`.\n\nTime complexity: `O(2^n)`, space complexity: `O(2^n)`.\n\n```\nclass Solution(object):\n    def subsetsWithDup(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: List[List[int]]\n        """\n        if not nums:\n            return [[]]\n        res = [[]]\n        dic = collections.Counter(nums)\n        for key, val in dic.items():\n            tmp = []\n            for lst in res:\n                for i in range(1, val+1):\n                    tmp.append(lst+[key]*i)\n            res += tmp\n        return res\n```\n\nSame idea, with a backtracking algorithm. Time complexity: `O(2^n)`, space complexity: `O(2^n)`.\n\n```\nclass Solution(object):\n    def subsetsWithDup(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: List[List[int]]\n        """\n        def helper(nums, i, j):\n            if i > j:\n                return [[]]\n            if j == i:\n                return [[],[nums[i]]]\n            tail = nums[j]\n            count = 0\n            k = j\n            while k >= i and nums[k] == tail:\n                count += 1\n                k -= 1\n            res = helper(nums, i, k)\n            for k in range(len(res)):\n                for l in range(1, count+1):\n                    res.append(res[k]+[tail]*l)\n            return res\n            \n        nums = sorted(nums)\n        return helper(nums, 0, len(nums)-1)\n```
[]