DSA problem
Subsets II
Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets, and the answer may be returned in any order. For example, with nums = [1,2,2], the subset [1,2] should appear only once even though there are two 2s in the input.
This is the duplicates-allowed variant of the standard subsets problem. A brute-force fix would enumerate every subset, push them into a set keyed by their sorted tuple, and return the deduplicated list. But that wastes time and memory generating subsets we are going to throw away — and it is also a leaky API, because the work scales with 2^n even when the unique answer is much smaller.
The clean fix is the standard "sort, then skip duplicates at the same recursion level" pattern. After sorting, any equal-value run sits in a contiguous block of indices. When the recursive loop picks an index, the first equal-value index in that block starts a fresh branch; every other index in the block (at the same depth) would generate an identical subtree, so we skip it with the rule if i > start && nums[i] == nums[i - 1] continue.
Everything else follows the regular subsets template: at every node snapshot path into the results, then iterate i from start to n - 1, push nums[i], recurse on i + 1, and pop. The dedupe rule fires O(n) times per level so total time stays at O(n * 2^n) worst case and space is O(n) for recursion and working buffer.
Examples
nums = [1,2,2][[],[1],[1,2],[1,2,2],[2],[2,2]]nums = [0][[],[0]]nums = [4,4,4,1,4][[],[1],[1,4],[1,4,4],[1,4,4,4],[1,4,4,4,4],[4],[4,4],[4,4,4],[4,4,4,4]]Constraints
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- The input array may contain duplicate values.
- The solution set must not contain duplicate subsets.
- You may return the answer in any order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.