Subsets II

Generate all unique subsets from an array that may contain duplicates.

subsets backtracking deduplication recursion

Write a function `subsets_with_dup(nums)` that takes a list of integers `nums` (which may contain duplicates) and returns a list of all possible unique subsets (the power set). The solution set must not contain duplicate subsets. Return the subsets in any order, but each subset itself should be sorted in non-decreasing order. The input list may be unsorted.

Constraints

- `0 <= len(nums) <= 15`
- `-10 <= nums[i] <= 10`
- The input list may contain duplicates.
- The output can be in any order.
- Each subset must be sorted in non-decreasing order.
- The total number of unique subsets is at most `2^n`, where `n` is the length of the input.

Example

>>> subsets_with_dup([1,2,2])
[[], [1], [1,2], [1,2,2], [2], [2,2]]
>>> subsets_with_dup([0])
[[], [0]]
>>> subsets_with_dup([])
[[]]

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort the input array first to make duplicates adjacent.

During backtracking, skip an element if it is the same as the previous element and the previous element was not included in the current subset.

Alternatively, use a set to store subsets but that may be less efficient; try to avoid duplicates during recursion.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.