Subset II

Problem: Subset II

For a dynamic-programming problem, we need to create a result space to store step 1 results. Then we can step 2, step 3, and final step results etc based on step 1. For this problem, we can make the empty set and first number as step 1 results. When we achieve a new number, we simply add it to all subsets we got to get new subsets. Of course we need to check whether the new subset was achieved before and sort all the numbers at very first.

Code in Python:

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        dp = {}
        dp[0] = [[], [nums[0]]]
        for i in xrange(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]