58ms AC Python Code without list comprehension


  • 2
    B
    class Solution:
        # @param num, a list of integer
        # @return a list of lists of integer
        def subsetsWithDup(self, S):
            if not S:
                return [[]]
            
            S.sort()
            result=[[]]
            
            for i in range(len(S)):
                addpart=[]
                if i>0 and S[i]==S[i-1]:
                    for item in oldresult:
                        add=item[:]
                        add.append(S[i])
                        addpart.append(add)
                else:
                    for item in result:
                        add=item[:]
                        add.append(S[i])
                        addpart.append(add)
    
                oldresult=addpart
    
                result.extend(addpart)
    
    
            return result
    

    At its bottom, this is a very good dynamic programming problem. For each item to consider, include it or not include it constitutes the complete subset up to this item. If you find a duplicate item, just ignore the part of old subset that does not include it yet.


Log in to reply
 

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