Leetcode 90. Subsets II

https://leetcode.com/problems/subsets-ii/

Still DFS. It might not be the best solution, while it is easy to use and clear to read.

Solution:

# T:O(n*2^n) S:O(1)
class Solution:
    # @param {integer[]} nums
    # @return {integer[][]}
    def subsetsWithDup(self, nums):
        if not nums: return [[]]
        N, ret = len(nums), [[]]
        nums.sort()
        def dfs(start, depth, valueList):
            if valueList not in ret:
                ret.append(valueList)
            if depth == N:
                return
            for i in xrange(start, N):
                dfs(i+1, depth+1, valueList+[nums[i]])
        dfs(0, 0, [])
        return ret

Run Time: 72 ms