Subsets With Duplicates
Solve this Problemnums that may repeat values. Produce every distinct subset it has — no two entries in the result may contain the same multiset of values, even though the same value might sit at more than one position in the input.
Treating every position as independent (as if all values were unique) overcounts: two different positions holding the same value can build the exact same subset. The fix is to only ever pick "the next occurrence of a repeated value" going deeper into a choice already made, never as a fresh alternative at the same decision point.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums.length ≤ 10 - ◆
-10 ≤ nums[i] ≤ 10 - ◆
nums may contain repeated values
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Generate All Then Deduplicate
BruteEnumerate every one of the 2ⁿ raw bit patterns exactly like the duplicate-free version, sort each resulting subset, and keep only the ones not already seen (tracked via a hash set of canonicalized keys). Correct, but every duplicate value multiplies the raw work: ten copies of the same number still force all 2¹⁰=1024 bit patterns to be built and checked, even though only 11 of them are actually distinct.
O(2ⁿ · n log n)O(2ⁿ · n)1class Solution {
2 public int[][] subsetsWithDup(int[] nums) {
3 int n = nums.length;
4 Set<String> seen = new HashSet<>();
5 List<int[]> result = new ArrayList<>();
6 for (int mask = 0; mask < (1 << n); mask++) {
7 List<Integer> subset = new ArrayList<>();
8 for (int i = 0; i < n; i++) {
9 if ((mask & (1 << i)) != 0) {
10 subset.add(nums[i]);
11 }
12 }
13 Collections.sort(subset);
14 String key = subset.toString();
15 if (seen.add(key)) {
16 int[] row = new int[subset.size()];
17 for (int j = 0; j < row.length; j++) {
18 row[j] = subset.get(j);
19 }
20 result.add(row);
21 }
22 }
23 return result.toArray(new int[0][]);
24 }
25}Optimal — Backtracking With Duplicate Skipping
OptimalSort nums first, so equal values sit next to each other. Then run the same include/exclude backtracking as the duplicate-free version, with one extra rule: at any recursion level, once a value has been tried as the FIRST new element added at that level, skip every identical value that follows it as a sibling choice. That one check prunes the duplicate branches before they're ever explored — for ten copies of the same value, only 11 nodes get visited instead of 1024.
O(2ⁿ · n)O(n) extra1class Solution {
2 public int[][] subsetsWithDup(int[] nums) {
3 int[] sorted = nums.clone();
4 Arrays.sort(sorted);
5 List<int[]> result = new ArrayList<>();
6 List<Integer> path = new ArrayList<>();
7 backtrack(sorted, 0, path, result);
8 return result.toArray(new int[0][]);
9 }
10
11 private void backtrack(int[] nums, int start, List<Integer> path, List<int[]> result) {
12 int[] row = new int[path.size()];
13 for (int j = 0; j < row.length; j++) {
14 row[j] = path.get(j);
15 }
16 result.add(row);
17 for (int i = start; i < nums.length; i++) {
18 if (i > start && nums[i] == nums[i - 1]) continue;
19 path.add(nums[i]);
20 backtrack(nums, i + 1, path, result);
21 path.remove(path.size() - 1);
22 }
23 }
24}