#90
Subsets II
Medium Backtracking with duplicate skip
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return all distinct subsets of an array that may contain duplicates.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: subsets without duplicates when the input has repeats.
Why this works: sort, then at the same level skip a value equal to the one just tried.
Example: [1, 2, 2]
[], [1], [1,2], [1,2,2], [2], [2,2]the second 2 is skipped as a starting choice at the same level
✦Hints open one at a time
Sort so equal values sit together.
At the same recursion level, skip a value equal to the previous one.
↗Approach
Same as Subsets, but sort first and inside the loop skip i > start with nums[i] == nums[i − 1]. That stops two branches at the same level from starting with the same value.
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), res);
return res;
}
private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
res.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue; // same value, same level
path.add(nums[i]);
backtrack(nums, i + 1, path, res);
path.remove(path.size() - 1);
}
}
}!Common mistake
Skipping with i > 0 instead of i > start, which also removes valid subsets like [2, 2].
Complexity
- Time: O(n · 2^n).
- Space: O(n).
Topic: Recursion & Backtracking
🎬 Episodes 29–36: video coming soon