Problem statement

https://leetcode.com/problems/subsets-ii/

Solution

It is quite classical problem and in python we can use functionality of language to make it oneliner. Imagine, that we have case [1, 1, 1, 2, 2, 3]. Then what subsets we have? We cah take:

  1. [], [1], [1, 1], [1, 1, 1] when we choose how many ones we take.
  2. [], [2], [2, 2] when we choose how many twos we take.
  3. [], [3] when we choose how many threes we take.

Our answer is all options when we take one element from first line, one from second and one from third and concatenate them. Let 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.

Complexity

Not 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.

class Solution:
    def subsetsWithDup(self, nums):
        return [chain(*i) for i in product(*[[[k]*i for i in range(v+1)] for k, v in Counter(nums).items()])]