14.11 Subsets II

14.11.1 Problem Metadata

14.11.2 Description

Given an integer array that may contain duplicates, return all possible subsets (the power set) without duplicates.

14.11.3 Examples

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

14.11.4 Constraints

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

14.11.5 Solution - Backtracking with Skip Logic

14.11.5.1 Walkthrough

This problem uses the 2-dimensional traversal mental model of backtracking (see Pattern 1: Choose-Explore-Unchoose):

  • Outer dimension (recursion parameter): start / depth in the decision tree - controls which subset of elements we’re considering
  • Inner dimension (for-loop): Iterates through available indices i from start to nums.length - 1 at each depth

The backtracking explores a conceptual grid where each row represents a depth level and each column represents a choice of including or excluding an element. At each node, we append the current path (representing one subset) to results.

Key mechanism: Sort nums so duplicates are adjacent. During recursion, skip elements equal to the previous when at the same depth (i > start && nums[i] == nums[i-1]) to avoid generating duplicate subsets.

14.11.5.2 Analysis

  • Time Complexity: O(2^n)
  • Space Complexity: O(n) recursion stack

14.11.5.3 Implementation Steps

  1. Sort nums to group duplicates together.
  2. Initialize empty result list to store all subsets.
  3. Define backtrack(nums, start, path, result):
    1. Add a copy of path to result (every path represents a valid subset).
    2. For each index i from start to nums.length - 1:
      • Skip if i > start and nums[i] == nums[i - 1] (avoid duplicate subsets)
      • Add nums[i] to path (choose)
      • Recursively call backtrack(nums, i + 1, path, result) (explore)
      • Remove last element from path (unchoose)
  4. Call backtrack(nums, 0, new ArrayList<>(), result) to start, then return result.

14.11.5.4 Code - Java

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

private void backtrack(int[] nums, int start, List<Integer> path,
                       List<List<Integer>> result) {
    // Add current subset to results (every path is a valid subset)
    result.add(new ArrayList<>(path));

    // Try adding each remaining element
    for (int i = start; i < nums.length; i++) {
        // Skip duplicates: only use first occurrence at each recursion level
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }

        // Choose: add current element
        path.add(nums[i]);

        // Explore: recurse with next start index
        backtrack(nums, i + 1, path, result);

        // Unchoose: remove element for next iteration
        path.remove(path.size() - 1);
    }
}