Subsets II

Description

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.

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

Example 2:
Input: nums = [0]
Output: [[],[0]]

Constraints:

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

Brute Force Solution (Standard Backtracking + Set)

Generate all $2^n$ possible subsets using simple recursion, sort each subset, and store them in a Set to filter out duplicates.

import java.util.*;
 
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); // Sort to ensure duplicate subsets match identical patterns
        Set<List<Integer>> resultSet = new HashSet<>();
        backtrack(nums, 0, new ArrayList<>(), resultSet);
        return new ArrayList<>(resultSet);
    }
 
    private void backtrack(int[] nums, int index, List<Integer> current, Set<List<Integer>> result) {
        if (index == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }
 
        // 1. Include nums[index]
        current.add(nums[index]);
        backtrack(nums, index + 1, current, result);
        current.remove(current.size() - 1);
 
        // 2. Exclude nums[index]
        backtrack(nums, index + 1, current, result);
    }
}
 

• Time Complexity: $O(2^n\cdot n)$ — $2^n$ subsets generated, copying each takes up to $O(n)$, plus set insertion cost.
• Space Complexity: $O(2^n\cdot n)$ — Storing duplicate subsets inside the Hash Set before returning.

---

Most Optimized & Intuitive Solution (Striver’s Pattern)

Intuition

Sort the array first so duplicate numbers are adjacent (e.g., [1, 2, 2]).
At every recursive step, we decide which element to add at the current position of our subset:

1. First Choice (i == start): Always valid. Pick nums[i] to start a branch.
2. Subsequent Choices (i > start): If nums[i] == nums[i - 1], skip it. We already explored an identical choice at this exact position level.

Decision Tree for nums = [1, 2, 2]
 
                     []
           /         |         \
        [1]         [2]        [2]  <-- SKIP! (i > start && nums[i] == nums[i-1])
       /   \         |
    [1,2]  [1,2]   [2,2]
     /       ^
 [1,2,2]   SKIP!
 

import java.util.*;
 
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); // Step 1: Group identical elements together
        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) {
        // Every valid node in the decision tree is a unique subset
        result.add(new ArrayList<>(current));
 
        for (int i = start; i < nums.length; i++) {
            // Step 2: Skip identical elements at the SAME decision level
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
 
            current.add(nums[i]);
            backtrack(nums, i + 1, current, result); // Move to next index
            current.remove(current.size() - 1);       // Backtrack
        }
    }
}
 

Complexity

• Time Complexity: $O(2^n\cdot n)$ — Generates only unique subsets (at most $2^n$). Copying each subset to result takes $O(n)$.
• Space Complexity: $O(n)$ — Recursion stack depth is at most $n$.

---

Easy Memory Rule

“Sort first. Inside the loop, if i > start and nums[i] == nums[i-1], skip it.”

What is Backtracking?

Backtracking is a trial-and-error algorithm technique. Think of it as exploring a maze:

1. You walk down a path making decisions.
2. If you reach a dead end (or complete a valid path), you step backward to the last intersection.
3. You try a different path from that same intersection.

In code, backtracking boils down to a 3-step blueprint inside a recursive function:

1. CHOOSE   --> Pick an option and add it to your current solution path.
2. EXPLORE  --> Recurse deeper to make the next set of choices.
3. UN-CHOOSE --> Remove the option (backtrack) to restore the state for the next choice.
 

---

How Backtracking Works in Subsets II

When generating subsets for nums = [1, 2, 2], we reuse a single list current throughout the entire recursion rather than copying array states at every single step.

Here is the exact code snippet for reference:

// 1. CHOOSE
current.add(nums[i]);
 
// 2. EXPLORE
backtrack(nums, i + 1, current, result);
 
// 3. UN-CHOOSE (The Backtrack Step)
current.remove(current.size() - 1);
 

Step-by-Step Execution Walkthrough (nums = [1, 2, 2])

                           []
                /           |           \
            [1]            [2]          [2] (Skipped!)
          /     \           |
      [1, 2]   [1, 2]     [2, 2]
        |      (Skipped!)
    [1, 2, 2]
 

1. Root Call (start = 0, current = [])

   • Add [] to result.

2. Branch 1: Pick 1 (i = 0)

   • Choose: Add 1 $\to$ current = [1]
   • Explore: Recurse to start = 1
   • Add [1] to result.
   • Sub-branch 1a: Pick first 2 (i = 1)
     • Choose: Add 2 $\to$ current = [1, 2]
     • Explore: Recurse to start = 2
     • Add [1, 2] to result.
   • Sub-sub-branch: Pick second 2 (i = 2)
     • Choose: Add 2 $\to$ current = [1, 2, 2]
     • Explore: Recurse to start = 3
     • Add [1, 2, 2] to result. Reaches end of loop.
     • Un-choose: Remove last 2 $\to$ current = [1, 2]
     • Loop finishes at this level.
     • Un-choose: Remove 2 $\to$ current = [1]
   • Sub-branch 1b: Try second 2 (i = 2)
     • i > start ($2>1$) and nums[2] == nums[1] $\to$ Skip duplicate!
     • Loop finishes at this level.
     • Un-choose: Remove 1 $\to$ current = [] (Back to clean slate!)

3. Branch 2: Pick first 2 (i = 1)

   • Choose: Add 2 $\to$ current = [2]
   • Explore: Recurse to start = 2
   • Add [2] to result.
   • Pick second 2 (i = 2) $\to$ current = [2, 2] $\to$ Add [2, 2] to result.
   • Un-choose: Remove 2 $\to$ current = [2].
   • Un-choose: Remove 2 $\to$ current = [].

4. Branch 3: Try second 2 (i = 2)

   • i > start ($2>0$) and nums[2] == nums[1] $\to$ Skip duplicate!

---

Why the “Un-choose” Step Matters

Without current.remove(current.size() - 1), the list current would continuously grow ([1], [1, 2], [1, 2, 2], [1, 2, 2, 2], ...) because memory would contaminate across different decision branches.

By immediately removing the item after the recursive call returns, current acts as a reusable workspace canvas, keeping the space complexity lean at $O(N)$ auxiliary space instead of allocating thousands of intermediate arrays.