Medium

Subsets II

LAB

Return all unique subsets of nums that may contain duplicates, sorted lexicographically.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    2,
    2
  ]
}

Output
[
  [],
  [
    1
  ],
  [
    1,
    2
  ],
  [
    1,
    2,
    2
  ],
  [
    2
  ],
  [
    2,
    2
  ]
]

FUNCTION SHAPE

nums: intArray→intMatrix

SOLUTION NOTE

We can apply the same template as before. The only thing is need to sort the subset, and make res a set. This is to prevent duplicates, where we consider permutations of the same subset as duplicates. (ie: [1,2], [2,1] are equivalent)

Reveal reference solution +

pythonREFERENCE

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    res = set()
    subset = []

    def backtrack(i):
        if i == len(nums):
            res.add(tuple(sorted(subset)))  # NEED to sort the subset... or else we can
            # get multiple permutations of the same combination... (ex. [1,2], [2,1])
        else:
            # use nums[i]
            subset.append(nums[i])
            backtrack(i+1)
            subset.pop()

            # do not use nums[i]
            backtrack(i+1)

    backtrack(0)
    return list(res)

# Alternative: leverage Subsets solution
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    return list(set(tuple(sorted(A)) for A in subsets(nums)))

TimeO(n*2^n)

SpaceO(n*2^n)

Open on LeetCode ↗