Problem
Given an integer array nums that may contain duplicate values, return all possible subsets. The solution set must not contain duplicate subsets. The order of the subsets does not matter.Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,2,2]Output
[[],[1],[1,2],[1,2,2],[2],[2,2]]Solution
This solution uses Backtracking to generate all possible subsets. The array is first sorted so that duplicate values appear next to each other.
The loop then chooses each possible element and recursively builds the next subset.
The condition
i > start && nums[i] == nums[i - 1] skips duplicate values at the same recursion level. This prevents generating duplicate subsets while still allowing the same value to be included multiple times when it comes from different positions.
After each recursive call, the last element is removed so that the algorithm can explore the next possible choice.
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, int start,
List<Integer> current, List<List<Integer>> result) {
// Every state represents a valid subset.
result.add(new ArrayList<>(current));
for (int i = start; i < nums.length; i++) {
// Skip duplicate values at the same recursion level.
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
// Choose the current element.
current.add(nums[i]);
// Continue with the next element.
backtrack(nums, i + 1, current, result);
// Undo the choice.
current.remove(current.size() - 1);
}
}
Complexity
There can be up to2n possible subsets. Since each subset can contain up to n elements, the time complexity is O(n × 2n) in the worst case.
Sorting the array takes
O(n log n), which is dominated by the backtracking cost for larger inputs.
The recursion depth is at most
O(n), excluding the space required for storing the output.