An Interactive Visual Explainer
You are given an array nums of integers, which may contain duplicates. Return all possible subsets.
The solution must not contain duplicate subsets. You may return the solution in any order.
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Input: nums = [0]
Output: [[],[0]]
1 <= nums.length <= 10-10 <= nums[i] <= 10// class Solution { ...
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// Step 1: Sort the array to handle duplicates
Arrays.sort(nums);
// Step 2: Start the backtracking process
backtrack(result, new ArrayList<>(), nums, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, int start) {
// Step 3: Add the current combination to the results list
result.add(new ArrayList<>(current));
// Step 4: Iterate through elements to form new subsets
for (int i = start; i < nums.length; i++) {
// Step 5: Skip duplicates
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
// Step 6: Include the element
current.add(nums[i]);
// Step 7: Recurse
backtrack(result, current, nums, i + 1);
// Step 8: Backtrack (remove the element)
current.remove(current.size() - 1);
}
}
// }This problem is a variation of "Subsets" with the added constraint of handling duplicate numbers in the input. The core backtracking logic remains the same: for each element, we decide to either "include" it or "not include" it in the current subset.
The key to avoiding duplicate subsets is to first sort the input array. Once sorted, all duplicate numbers will be adjacent. Then, within our recursive function's loop, we add a condition: if the current element is the same as the previous one, and we are not at the very beginning of the loop for this level of recursion (i.e., `i > start`), we skip the current element.
This works because on any given level of recursion, we only want to generate subsets starting with a particular number *once*. For example, if we have `[1, 2, 2]`, after we generate all subsets starting with the first `2` (like `[1, 2]` and `[1, 2, 2]`), we don't need to do it again for the second `2`, as it would produce the exact same subsets.
Current Subset
-
Current Index (i)
-
Hello, and welcome to the interactive explainer for LeetCode problem 90: Subsets II.
This problem is similar to the original Subsets problem, but with a twist: the input array can contain duplicate numbers. Our goal is to find all possible unique subsets.
The solution again uses backtracking. However, to handle the duplicates correctly, our first step is to sort the input array. This places all identical elements next to each other, which is key for our duplicate-handling logic.
The recursive function works much like before. At each step, we add the current subset to our results list. Then, we loop through the remaining elements to make our next "choice". Here comes the crucial new part: inside the loop, before we decide to include an element, we check if it's a duplicate. The condition is: if the current index `i` is greater than the starting index `start` for this recursive call, AND the current element `nums[i]` is the same as the previous element `nums[i-1]`, we `continue` to the next iteration, effectively skipping this element and all recursive paths it would have generated. This prevents us from creating duplicate subsets.
If the element is not a duplicate, we proceed as normal: we "include" it in our current subset, make a recursive call starting from the next index `i + 1`, and after that call returns, we "backtrack" by removing the element. This ensures that for any level of recursion, we only consider each unique number once, pruning the decision tree and guaranteeing a unique set of subsets in the final result.