My DP solution in python 84s


  • 0
    F

    Difference between subset 1 is just add a condition to check if this array is already in previous result when create new arrays, but probably need further optimize, run time is 84s.

    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        dp={}
        dp[0]=[[],[nums[0]] ] 
    
        for i in range(1,len(nums)):
            dp[i]=dp[i-1]+[x+[nums[i]] for x in dp[i-1] if x+[nums[i]] not in dp[i-1]]
        return dp[len(nums)-1]

Log in to reply
 

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