Non-recursive O(N^2) solution


  • 0
    L

    The idea is to add the current element in the sorted nums to each subset of the result from previous loop, and add those new sets to the result. If there are no duplicated element in the input nums, the result will be double in size at each loop. It avoided using recursion with expense of checking if new element is already in the result set. There are tradeoffs but it can still be done in 80ms.

    class Solution:
        # @param {integer[]} nums
        # @return {integer[][]}
        def subsetsWithDup(self, nums):
            nums.sort()
            ret = set()
            ret.add(tuple([]))
            for num in nums:
                new_set = set()
                for i, ele in enumerate(ret):
                    new_ele = tuple(list(ele) + [num])
                    new_set.add(new_ele)
                ret = ret | new_set
            return [list(x) for x in ret]

  • 0
    Y

    The size of ret grows exponentially thus the time complexity shouldn't be O(N^2)


Log in to reply
 

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