Accepted python submission (67ms) with explanation


  • 0
    L

    the code recursively calculate the subset. The all subsets of the list without the first elements once calculated as L1, the answer would be L1+S[0]+all list in L1. That's the answer for the case without duplicates. When duplicates exists, the duplicated subset need to be removed. To avoid the redundant calculation, the code filters out the duplicates only when they exist. That is when S[0]==S[1](EG. S=[1,1,2]).

    class Solution:
        # @param num, a list of integer
        # @return a list of lists of integer
        def subsetsWithDup(self, S):
            res=[[]]
            if S:
                S.sort()
                subSet=self.subsetsWithDup(S[1:])
                if len(S)>1 and S[0]==S[1]:
                    # duplicates exists only when first two elements are identical
                    res=subSet+[[S[0]]+set for set in subSet if (([S[0]]+set) not in subSet)]
                else:
                    res=subSet+[[S[0]]+set for set in subSet]
            return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.