Editor

Every Subset, No Repeats

#116 · Recursion and backtracking · Advanced · 110 XP · about 18 min

A subset is any selection of items from a collection, from none of them to all of them. Write unique_subsets(nums) that returns every different subset of the list nums, which may contain repeated values.

Two subsets are the same when they hold the same values the same number of times, whichever copies were picked. Write each subset as a list in increasing order, and return the list of subsets sorted too, in Python's ordering of lists (so [] comes first and [1, 2] comes before [2]).

Examples

unique_subsets([2, 1, 2])  # returns [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
unique_subsets([3, 1])     # returns [[], [1], [1, 3], [3]]
unique_subsets([])         # returns [[]]

In the first example there are 8 ways to pick from three items, but picking the first 2 or the second 2 gives the same subset, so only 6 different subsets remain.

Constraints

  • 0 <= len(nums) <= 15
  • -10 <= nums[i] <= 10

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.