[Python] Oneliner with product, explained
It is quite classical problem and in python we can use functionality of language to make it oneliner.\nImagine, that we have case [1, 1, 1, 2, 2, 3]. Then what 
It is quite classical problem and in python we can use functionality of language to make it oneliner.\nImagine, that we have case `[1, 1, 1, 2, 2, 3]`. Then what subsets we have? We cah take:\n1. `[], [1], [1, 1], [1, 1, 1]` when we choose how many ones we take.\n2. `[], [2], [2, 2]` when we choose how many twos we take.\n3. `[], [3]` when we choose how many threes we take.\n\nOur answer is all options when we take one element from first line, one from second and one from third and concatenate them.\nLet us look at `[[[k]*i for i in range(v+1)] for k, v in Counter(nums).items()]` in mor details: what we have is `A = [[[], [1], [1, 1], [1, 1, 1]], [[], [2], [2, 2]], [[], [3]]]`. Now, what we need to do is to use functionality of product: we want to take elements from `A[0]`, `A[1]` and `A[2]` and for this we use trick `[chain(*i) for i in product(*A)]`, where `*` used to let product know that we want to give each element `A[0], A[1], A[2]` as parameter of product: try to do `product([[1,2,3],[4,5]])` and `product(*[[1,2,3],[4,5]])` and see the difference. The same trick is used for chain.\n\n#### Complexity\nNot very tight bound for time complexity is `O(2^n*n)`, where `n` is total number of elements, space complexity as well. In fact complexity (time and space) is `O((a1+1)*...*(ak+1)*n)`, where `a1, ..., ak` are frequencies of each element.\n\n```python\nclass Solution:\n    def subsetsWithDup(self, nums):\n        return [chain(*i) for i in product(*[[[k]*i for i in range(v+1)] for k, v in Counter(nums).items()])]\n```\n\nIf you have any question, feel free to ask. If you like the explanations, please **Upvote!**
[]