All problems

Subsets II

Medium · backtracking

Given a list nums of integers that may contain repeated values, return every distinct subset, including the empty subset and the full list.

A subset is a selection of entries from nums; the order of the entries in the original list does not matter, so [1, 2] and [2, 1] are the same subset. Write the numbers inside each subset in ascending order. Two subsets are the same when they contain the same values the same number of times, and each distinct subset must appear exactly once in the answer. The subsets may be returned in any order.

Examples

Example 1

Input: nums = [3, 1, 3]

Output: [[], [1], [3], [1, 3], [3, 3], [1, 3, 3]]

There are two 3s, so [3] could be chosen in two ways, but it is listed once. [3, 3] uses both of them.

Example 2

Input: nums = [0, 0]

Output: [[], [0], [0, 0]]

Only the number of zeros chosen matters: none, one or two.

Example 3

Input: nums = [-1]

Output: [[], [-1]]

Constraints