Subsets II

Share

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.

Example 1
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Explanation: Although 2 appears twice, each unique subset is listed only once.
Example 2
Input: nums = [0]
Output: [[],[0]]

Solution Approach

The key insight is to sort the array first so that duplicate values are adjacent. During backtracking, when we are at the same recursion depth and we see the same value as the previous sibling (i.e., nums[i] == nums[i-1] and i > start), we skip it to avoid generating duplicate subsets.

  • Sort nums so duplicates are adjacent.
  • In the loop, if i > start and nums[i] == nums[i-1], skip this index.
  • Otherwise proceed identically to Subsets: add current snapshot, recurse with i+1, backtrack.
Java
import java.util.*;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); // sort to group duplicates
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start,
                           List<Integer> current,
                           List<List<Integer>> result) {
        result.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            // Skip duplicate elements at the same tree level
            if (i > start && nums[i] == nums[i - 1]) continue;
            current.add(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}
Complexity Analysis:

Time complexity: O(n * 2^n) in the worst case (all elements distinct).
Space complexity: O(n) for the recursion stack.