subsets_2.py

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        output= []
        self.gen_subsets(sorted(nums),0,[],output)
        return output
      

    def gen_subsets(self,a,i,sofar,output):
        n = len(a)
        if i==n:
            output.append(sofar[:])
            return
        
        # Choice 1: Pick elemet a[i] to be in subset
        sofar.append(a[i])
        self.gen_subsets(a,i+1,sofar,output)
        sofar.pop()
        
        # Choice 2:Don't pick element a[i] to be in subset
        # But can only make this choice if a[i] is not the same as the last element added to path
        #
        if not sofar or sofar[-1] != a[i]:
            self.gen_subsets(a,i+1,sofar,output)

            
    
    '''
    Think of what the subsets of a duplicate array must look like
    [a,a,a,a] => (), (a), (a,a), (a,a,a), (a,a,a,a)
    So, for a 4 elememnt array, we get 1 + 4 subsets.  1 being the empty subset
    
    
    Now think of how we can avoid duplicates.
    [a,a,a,a]
    if we make 2 choices at each step, 
    we will end up with duplciates, because we can pick a,a,a in 4 different ways.
    We can pick a0,a1,a2 or a0,a1,a3 or a0,a2,a3 or a1,a2,a3
    
    So to avoid these duplciates,
    once we have an element say A already in the path/subset,
    when we encounter another A, we only have 1 choice, i.e to pick it.
    We will not have the choice to not pick it.
    
    '''