Haven't see DP solution, here it is


  • 8
    F

    For this question, DP or recursive or backtrack what ever, I think it's almost same thing,but let's do it in a pure DP way:

    1 Start from only 1 dig in the list, then result is obvious, [[],[nums[0]]]

    2 Than for each new dig, the result is the previous list + previous list append the new dig,
    it's easy to understand, since once the new dig come in, there is 2 options, with it or with out it.
    without it, is the previous result, with it, it to add this dig in each array of the previuos result

    def subnets(nums):
        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]]
        return dp[len(nums)-1]

  • 0
    B

    I used copy library. But I think your solution with dictionary is more efficient! Thank you for the tips!

    import copy
    class Solution(object):
        def subsets(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            result=[[]]
            n=len(nums)
            nums.sort()
            for i in range(n):
                c = copy.deepcopy(result)
                for k in c:
                    k.append(nums[i])
                    result.append(k)
            return result

Log in to reply
 

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