Skip to content
AI360Xpert
Back to Backtracking
Medium

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. Return the solution in any order.

Examples

Input:nums = [1,2,2]
Output:[[],[1],[1,2],[1,2,2],[2],[2,2]]
Note that [1,2] appears once, and we do not have duplicate subsets even though the input contains two 2s.
Input:nums = [0]
Output:[[],[0]]
With a single unique element, the result is the empty set and the set containing the element.

Constraints

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

Backtracking with Sorting

Approach

To handle duplicates, we first sort the array. This ensures that duplicate elements are adjacent to each other. During backtracking, when we are iterating through possible elements to include, if the current element is the same as the previous one and we are at the same depth level (i > index), we skip it to avoid creating duplicate subsets.

Complexity Analysis

Time Complexity
O(n * 2^n)
Space Complexity
O(n)

Sorting takes O(n log n) time. Generating all subsets takes O(n * 2^n) time. The overall time complexity is dominated by the subset generation. Space complexity is O(n) for the recursion stack and the temporary list.

Solution.java
class Solution {    public List<List<Integer>> subsetsWithDup(int[] nums) {        List<List<Integer>> result = new ArrayList<>();        // Sort the array to handle duplicates        Arrays.sort(nums);        backtrack(0, nums, new ArrayList<>(), result);        return result;    }        private void backtrack(int index, int[] nums, List<Integer> current, List<List<Integer>> result) {        // Add the current subset to the result        result.add(new ArrayList<>(current));                // Explore further elements to include        for (int i = index; i < nums.length; i++) {            // Skip duplicates at the same level of the recursion tree            if (i > index && nums[i] == nums[i - 1]) {                continue;            }                        // Include the current element            current.add(nums[i]);                        // Recurse with the next index            backtrack(i + 1, nums, current, result);                        // Backtrack by removing the added element            current.remove(current.size() - 1);        }    }}