# Subsets II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/subsets-ii)
Canonical: https://scaleengineer.com/dsa/problems/subsets-ii
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Google](https://scaleengineer.com/companies/google), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [TikTok](https://scaleengineer.com/companies/tiktok), [Swiggy](https://scaleengineer.com/companies/swiggy)
---
## Problem
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`

# Approaches
## Brute Force with Set
This approach first generates all possible subsets, including duplicates, using a standard recursive technique. It then leverages a `HashSet` to automatically filter out the duplicate subsets, leaving only the unique ones.
**Time:** O(n * 2^n) · **Space:** O(n * 2^n)
**Pros:** Simple to understand as it separates the logic of subset generation from duplicate handling.
**Cons:** Highly inefficient as it generates all `2^n` possible paths, including many that lead to duplicate subsets which are then discarded.; The overhead of using a `HashSet` for storing lists, which involves computing hash codes for each list, adds to the performance cost.
### Explanation
The core idea is to treat the problem as if there were no duplicates in the input array, and then handle the duplicates as a post-processing step. We use a standard recursive backtracking algorithm where for each element, we decide whether to include it in the current subset or not. This generates `2^n` subsets in total.

Since the input array `nums` can contain duplicates, this process will inevitably generate identical subsets. For example, given `[1, 2, 2]`, the subset `[1, 2]` can be formed by picking `1` and the first `2`, and also by picking `1` and the second `2`.

To eliminate these duplicates, we store each generated subset in a `HashSet<List<Integer>>`. Before starting, we sort the input array `nums`. This ensures that any duplicate subsets we generate will have their elements in the same order (e.g., we'll generate `[1, 2]` twice, not `[1, 2]` and `[2, 1]`), which is essential for the `HashSet` to recognize them as identical. Finally, we convert the `HashSet` back to a `List` for the final output.

```java
import java.util.*;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Set<List<Integer>> resultSet = new HashSet<>();
        // Sort the array to ensure duplicate subsets are identical in order.
        Arrays.sort(nums);
        generateSubsets(0, new ArrayList<>(), nums, resultSet);
        return new ArrayList<>(resultSet);
    }

    private void generateSubsets(int index, List<Integer> currentSubset, int[] nums, Set<List<Integer>> resultSet) {
        // Base case: when we've considered all numbers.
        if (index == nums.length) {
            resultSet.add(new ArrayList<>(currentSubset));
            return;
        }

        // Recursive step 1: Don't include the current element.
        generateSubsets(index + 1, currentSubset, nums, resultSet);

        // Recursive step 2: Include the current element.
        currentSubset.add(nums[index]);
        generateSubsets(index + 1, currentSubset, nums, resultSet);
        
        // Backtrack: remove the element to explore other paths.
        currentSubset.remove(currentSubset.size() - 1);
    }
}
```
### Algorithm
1. Sort the input array `nums`. This is crucial for the `HashSet` to correctly identify duplicate lists, as it ensures they have the same element order.
2. Initialize a `HashSet<List<Integer>>` to store the unique subsets.
3. Define a recursive helper function, `generate(index, currentSubset)`.
4. **Base Case:** If `index` reaches the end of `nums`, it means we have formed a potential subset. Add a copy of `currentSubset` to the `HashSet`.
5. **Recursive Step:** For each element `nums[index]`, we explore two possibilities:
    a. **Exclude:** Make a recursive call to explore subsets without the current element: `generate(index + 1, currentSubset)`.
    b. **Include:** Add `nums[index]` to `currentSubset`, then make a recursive call: `generate(index + 1, currentSubset)`.
6. **Backtrack:** After the 'include' path returns, remove `nums[index]` from `currentSubset` to restore its state for other recursive paths.
7. Start the process by calling `generate(0, new ArrayList<>())`.
8. After the recursion completes, convert the `HashSet` of subsets into an `ArrayList` and return it.

## Iterative Approach
This approach builds the list of subsets iteratively, without using recursion. It starts with an empty set and progressively adds elements from the input array to generate new subsets. Sorting the array first is key to an efficient duplicate-handling strategy.
**Time:** O(n * 2^n) · **Space:** O(n * 2^n)
**Pros:** Avoids recursion, which eliminates the risk of stack overflow on very deep recursion trees (not an issue for this problem's constraints).; Can be slightly more performant by avoiding the overhead of recursive function calls.
**Cons:** The logic for managing the `startIndex` to handle duplicates can be less intuitive than the recursive backtracking approach.
### Explanation
The iterative solution begins by sorting the input array `nums` to group duplicates together. We initialize our `result` list with the empty subset, `[]`.

We then iterate through the sorted `nums` array. For each number, we create new subsets by adding it to existing ones. The crucial logic lies in how we handle duplicates:

- If the current number `nums[i]` is unique (i.e., not the same as `nums[i-1]`), we add it to *all* subsets currently in our `result` list to form new subsets.
- If `nums[i]` is a duplicate, we add it *only* to the subsets that were created in the previous step (i.e., the ones created using `nums[i-1]`). This prevents generating duplicate subsets. For example, with `[1, 2, 2]`, after processing `1`, we have `[[], [1]]`. When we process the first `2`, we add it to both, getting `[[], [1], [2], [1, 2]]`. For the second `2`, we only add it to the subsets just created (`[2]` and `[1, 2]`), resulting in `[2, 2]` and `[1, 2, 2]`, thus avoiding redundant combinations.

We manage this by keeping track of the size of the `result` list before processing each number.

```java
import java.util.*;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>()); // Start with the empty set

        int startIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            int currentSize = result.size();
            // If the current element is a duplicate, start adding it only to the subsets created in the previous step.
            int start = (i > 0 && nums[i] == nums[i - 1]) ? startIndex : 0;
            
            for (int j = start; j < currentSize; j++) {
                List<Integer> newSubset = new ArrayList<>(result.get(j));
                newSubset.add(nums[i]);
                result.add(newSubset);
            }
            // The starting point for the next potential duplicate is the size of the list before this iteration.
            startIndex = currentSize;
        }
        return result;
    }
}
```
### Algorithm
1. Sort the input array `nums`.
2. Initialize `result` with an empty subset: `result = new ArrayList<>(); result.add(new ArrayList<>());`.
3. Keep track of `startIndex`, which marks the beginning of subsets added in the previous iteration. Initialize it to `0`.
4. Iterate through `nums` from `i = 0` to `nums.length - 1`.
5. Determine the starting point for the inner loop. If `i > 0` and `nums[i] == nums[i-1]` (a duplicate), set `start = startIndex`. Otherwise, set `start = 0`.
6. Get the current size of the `result` list, let's call it `currentSize`.
7. Iterate from `j = start` to `currentSize - 1`. For each subset `result.get(j)` in this range:
    a. Create a `newSubset` by copying `result.get(j)`.
    b. Add `nums[i]` to `newSubset`.
    c. Add `newSubset` to the `result` list.
8. After the inner loop, update `startIndex` to `currentSize`. This marks the point where the subsets generated with `nums[i]` begin, which is needed for the next iteration if it encounters a duplicate.
9. Return `result`.

## Backtracking with Duplicate Pruning
This is the most common and elegant solution, utilizing a backtracking algorithm. By sorting the input array first, we can add a simple condition to the recursive function to intelligently prune the search space and avoid generating duplicate subsets from the outset.
**Time:** O(n * 2^n) · **Space:** O(n * 2^n)
**Pros:** Highly efficient as it prunes the search tree, avoiding the generation of duplicate subsets altogether.; The backtracking pattern is very powerful and can be adapted to solve a wide range of combinatorial problems (permutations, combinations, etc.).; The code is clean and expresses the logic of the search process clearly.
**Cons:** The use of recursion can incur a small overhead compared to an iterative solution, though it's often negligible.; For extremely large `n`, recursion could lead to a stack overflow, but this is not a concern with the given constraints (`n <= 10`).
### Explanation
This approach refines the standard backtracking template to handle duplicates. The first and most critical step is to sort the input array `nums`. This places all duplicate elements next to each other, which is the foundation for our duplicate-avoidance logic.

The backtracking function explores paths to build subsets. At each level of recursion, we iterate through the available numbers. The key insight is this: if we have a sequence of duplicate numbers (e.g., `[2, 2, 2]`), we only want to start a new recursive branch with the *first* `2`. Any subsets starting with the second or third `2` would be duplicates of those starting with the first `2`.

We enforce this with the condition `if (i > start && nums[i] == nums[i-1]) continue;`. Here, `start` is the index in `nums` where the current level of recursion begins its loop. If `i > start`, it means we are not at the first element of the loop for this recursive call. If, in addition, `nums[i]` is the same as `nums[i-1]`, we skip it. This ensures that for a set of duplicates, we only pick the first one to create a new branch of subsets.

```java
import java.util.*;

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

    private void backtrack(List<List<Integer>> result, List<Integer> currentSubset, int[] nums, int start) {
        result.add(new ArrayList<>(currentSubset));
        for (int i = start; i < nums.length; i++) {
            // This is the crucial part: if the current element is a duplicate of the previous one,
            // and we are not at the start of the loop for this level, skip it.
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            currentSubset.add(nums[i]);
            backtrack(result, currentSubset, nums, i + 1);
            currentSubset.remove(currentSubset.size() - 1); // Backtrack
        }
    }
}
```
### Algorithm
1. Sort the input array `nums` to group identical elements together.
2. Initialize an empty list `result` to store all the subsets.
3. Define a recursive helper function `backtrack(result, currentSubset, nums, start)`.
4. Inside `backtrack`, first add a copy of the `currentSubset` to the `result` list. This captures the subset at the current state.
5. Iterate through the `nums` array with an index `i` from `start` to the end.
6. **Pruning Condition:** Inside the loop, check if `i > start` and `nums[i] == nums[i-1]`. If true, it means we are about to create a duplicate subset, so we `continue` to the next iteration, effectively pruning this branch of the recursion tree.
7. **Include:** Add the current element `nums[i]` to `currentSubset`.
8. **Recurse:** Make a recursive call `backtrack(result, currentSubset, nums, i + 1)`. The next starting point is `i + 1` to ensure we only consider elements that appear after the current one.
9. **Backtrack:** Remove the last element from `currentSubset` to explore other possibilities.
10. Initiate the process by calling `backtrack(result, new ArrayList<>(), nums, 0)`.
11. Return the `result` list.

# Solutions
### CSharp

```csharp
public class Solution { private IList < IList < int >> ans = new List < IList < int >>(); private IList < int > t = new List < int >(); private int [] nums ; public IList < IList < int >> SubsetsWithDup ( int [] nums ) { Array . Sort ( nums ); this . nums = nums ; Dfs ( 0 ); return ans ; } private void Dfs ( int i ) { if ( i >= nums . Length ) { ans . Add ( new List < int >( t )); return ; } t . Add ( nums [ i ]); Dfs ( i + 1 ); t . RemoveAt ( t . Count - 1 ); while ( i + 1 < nums . Length && nums [ i + 1 ] == nums [ i ]) { ++ i ; } Dfs ( i + 1 ); } }
```

### Java

```java
class Solution {
public
  List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    List<List<Integer>> ans = new ArrayList<>();
    for (int mask = 0; mask < 1 << n; ++mask) {
      List<Integer> t = new ArrayList<>();
      boolean ok = true;
      for (int i = 0; i < n; ++i) {
        if ((mask >> i & 1) == 1) {
          if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
            ok = false;
            break;
          }
          t.add(nums[i]);
        }
      }
      if (ok) {
        ans.add(t);
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[][]} */ var subsetsWithDup =
  function (nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const t = [];
    const ans = [];
    const dfs = (i) => {
      if (i >= n) {
        ans.push([...t]);
        return;
      }
      t.push(nums[i]);
      dfs(i + 1);
      t.pop();
      while (i + 1 < n && nums[i] === nums[i + 1]) {
        i++;
      }
      dfs(i + 1);
    };
    dfs(0);
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> subsetsWithDup(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> ans;
    for (int mask = 0; mask < 1 << n; ++mask) {
      vector<int> t;
      bool ok = true;
      for (int i = 0; i < n; ++i) {
        if ((mask >> i & 1) == 1) {
          if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
            ok = false;
            break;
          }
          t.push_back(nums[i]);
        }
      }
      if (ok) {
        ans.push_back(t);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: def dfs(u, t): ans . append(t[:])  # or, t.copy() for i in range ( u , len ( nums )): # also good for [1,5,5], second '5' will be skipped here if # but second '5' is always covered, because i==u when ans=[1,5] and i=2 if i != u and nums [ i ] == nums [ i - 1 ]: continue t . append ( nums [ i ]) dfs ( i + 1 , t ) t . pop () ans = [] nums . sort () dfs ( 0 , []) return ans # iteration class Solution : def subsetsWithDup ( self , nums : List [ int ]) -> List [ List [ int ]]: if not nums : return [[]] nums . sort () # Sorting is necessary to handle duplicates. result = [[]] start_idx = 0 # Start index for the new subsets new_subsets_size = 0 for i in range ( len ( nums )): size = len ( result ) # If the current number is the same as the previous one, # we only want to extend the subsets added in the previous iteration. if i > 0 and nums [ i ] == nums [ i - 1 ]: start_idx = size - new_subsets_size else : start_idx = 0 new_subsets_size = 0 # Reset the size of newly created subsets for j in range ( start_idx , size ): current_subset = result [ j ] + [ nums [ i ]] result . append ( current_subset ) new_subsets_size += 1 return result ############ class Solution : def subsetsWithDup ( self , nums : List [ int ]) -> List [ List [ int ]]: nums . sort () n = len ( nums ) ans = [] for mask in range ( 1 << n ): ok = True t = [] for i in range ( n ): if mask >> i & 1 : if i and ( mask >> ( i - 1 ) & 1 ) == 0 and nums [ i ] == nums [ i - 1 ]: ok = False break t . append ( nums [ i ]) if ok : ans . append ( t ) return ans

```