Subsets II
Medium · Backtracking · Array · Backtracking · Bit Manipulation
Problem
Given an integer array nums that may contain repeated values, return every possible subset of its elements.
The result must not contain the same subset twice: two subsets are the same when they hold the same values the same number of times. The subsets, and the values inside each subset, may be returned in any order.
Examples
Input: nums = [3,1,3] Output: [[],[1],[1,3],[1,3,3],[3],[3,3]]
The two 3s are interchangeable, so a subset with one 3 is listed only once.
Input: nums = [5] Output: [[],[5]]
A single element is either left out or taken.
Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Six distinct subsets: [], [1], [1,2], [1,2,2], [2], [2,2].
Constraints
- 1 <= len(nums) <= 10
- -10 <= nums[i] <= 10
Approaches
- Baseline: every bitmask, deduplicated — time O(n · 2^n), space O(n · 2^n)
Follow-up
Another way to see it: if a value appears c times, a subset takes 0 to c copies of it, so the answer has the product of (c + 1) over the distinct values. The use cases apply the same skip rule to non-decreasing subsequences, where the input cannot be sorted and a set per level does the job, and to picks of exactly k values.
Related problems
Start free on Cariara · Coding problems · System design studio
