Subsets II

Subsets II is Subsets with one nasty twist. Now the array can have repeated numbers. So the plain backtracking will produce the same subset more than once. The real test here is how you stop those repeats cleanly. The fix is small but easy to get wrong.

🎯 The Problem

You get an array that may contain duplicate numbers. You must return all subsets, with no subset repeated.

• The input may hold repeated numbers, like two 2 values.
• A subset like [1, 2] can form using the first 2 or the second 2.
• Both give the exact same subset.
• You must keep only one copy of each subset.
• The order of the subsets does not matter.

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

Explanation: subsets like [1,2] appear once even though two 2 values could form it.

Here is the trouble drawn out. Picking the first 2 then later picking the second 2 on its own branch can land you on the same subset twice.

🐢 Approach 1: Generate All Then Dedupe With a Set (Brute Force)

The idea in one line: build every subset like plain Subsets, then throw away the repeats.

The idea:

• Run the normal Subsets backtracking, ignoring duplicates.
• Sort each subset so equal subsets look identical.
• Put each sorted subset into a set of seen subsets.

How it works:

• The set drops any subset it has seen before.
• At the end, the set holds one copy of each distinct subset.

Why it is weak:

• It still builds every duplicate before throwing it away.
• It needs extra work to sort and hash each subset.
• For an array of many equal values, the wasted branches pile up.

Here is the generate-then-dedupe code:

def subsets_with_dup(nums):
    result = set()

    def dfs(index, path):
        if index == len(nums):
            result.add(tuple(sorted(path)))
            return
        dfs(index + 1, path)
        dfs(index + 1, path + [nums[index]])

    dfs(0, [])
    return [list(item) for item in sorted(result)]

⚡ Approach 2: Sort Then Skip Equal Siblings (Best)

The idea in one line: sort first, then at each level skip a value equal to its left neighbour.

The idea:

• Sort the array so equal numbers sit next to each other.
• Now duplicates are neighbours, which makes them easy to spot.
• Skip a value when it equals the one just before it at the same level.

How it works:

• The test is i > start and nums[i] == nums[i - 1], then continue.
• The first equal value at a level runs and covers every subset that uses it.
• A second equal value at the same level would only repeat those branches, so skip it.

The i > start detail:

• We only skip equal siblings, meaning equal values picked at the same level.
• We still allow an equal value deeper down, as part of the same path.
• That is the difference between [2,2], which is valid, and a duplicate [2] branch, which is not.

Why it is fast:

• We never build a duplicate in the first place, so nothing is thrown away.
• Sorting is what makes “equal siblings sit next to each other” true, so it comes first.

This dry run shows the skip in action on the sorted array.

Steps to Solve

1. Sort the array so equal numbers sit next to each other.
2. Create a result list and start a recursive helper with an empty path and start index 0.
3. At the top of each call, record a copy of the current path.
4. Loop from the start index to the end.
5. If i > start and the current number equals the previous number, skip it with continue.
6. Otherwise add the number to the path. This is the choose step.
7. Recurse with the start index moved one past the current number.
8. Remove the number you just added. This is the un-choose step.

#include <stdio.h>

int nums[] = {1, 2, 2};
int n = 3;
int path[3];

void printSubset(int len) {
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d", path[i]);
        if (i < len - 1) printf(",");
    }
    printf("]\n");
}

void backtrack(int start, int len) {
    printSubset(len);                          // record current subset
    for (int i = start; i < n; i++) {
        if (i > start && nums[i] == nums[i - 1]) // skip equal sibling
            continue;
        path[len] = nums[i];                   // choose
        backtrack(i + 1, len + 1);             // explore
        // overwrite next loop = un-choose
    }
}

int main(void) {
    // sort so duplicates are neighbours
    for (int a = 0; a < n; a++)
        for (int b = 0; b < n - 1; b++)
            if (nums[b] > nums[b + 1]) {
                int t = nums[b]; nums[b] = nums[b + 1]; nums[b + 1] = t;
            }
    backtrack(0, 0);
    return 0;
}

[]
[1]
[1,2]
[1,2,2]
[2]
[2,2]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> result;
vector<int> path;

void backtrack(vector<int>& nums, int start) {
    result.push_back(path);                       // record current subset
    for (int i = start; i < (int)nums.size(); i++) {
        if (i > start && nums[i] == nums[i - 1])  // skip equal sibling
            continue;
        path.push_back(nums[i]);                  // choose
        backtrack(nums, i + 1);                   // explore
        path.pop_back();                          // un-choose
    }
}

int main() {
    vector<int> nums = {1, 2, 2};
    sort(nums.begin(), nums.end());               // duplicates become neighbours
    backtrack(nums, 0);
    for (auto& s : result) {
        cout << "[";
        for (int i = 0; i < (int)s.size(); i++) {
            cout << s[i];
            if (i < (int)s.size() - 1) cout << ",";
        }
        cout << "]" << endl;
    }
    return 0;
}

[]
[1]
[1,2]
[1,2,2]
[2]
[2,2]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SubsetsII {
    static List<List<Integer>> result = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();

    static void backtrack(int[] nums, int start) {
        result.add(new ArrayList<>(path));            // record current subset
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1])  // skip equal sibling
                continue;
            path.add(nums[i]);                        // choose
            backtrack(nums, i + 1);                   // explore
            path.remove(path.size() - 1);             // un-choose
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 2};
        Arrays.sort(nums);                            // duplicates become neighbours
        backtrack(nums, 0);
        System.out.println(result);
    }
}

[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

def subsets_with_dup(nums):
    nums.sort()                         # duplicates become neighbours
    result = []
    path = []

    def backtrack(start):
        result.append(path[:])          # record current subset (a copy)
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:  # skip equal sibling
                continue
            path.append(nums[i])        # choose
            backtrack(i + 1)            # explore
            path.pop()                  # un-choose

    backtrack(0)
    return result


print(subsets_with_dup([1, 2, 2]))

[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

function subsetsWithDup(nums) {
  nums.sort((a, b) => a - b);           // duplicates become neighbours
  const result = [];
  const path = [];

  function backtrack(start) {
    result.push([...path]);             // record current subset (a copy)
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue; // skip equal sibling
      path.push(nums[i]);               // choose
      backtrack(i + 1);                 // explore
      path.pop();                       // un-choose
    }
  }

  backtrack(0);
  return result;
}

console.log(JSON.stringify(subsetsWithDup([1, 2, 2])));

[[],[1],[1,2],[1,2,2],[2],[2,2]]

Let us walk through the Python version line by line, because the skip rule is the part that trips people up.

nums.sort() puts equal numbers side by side. This is required. The whole skip trick depends on duplicates being neighbours, and sorting is what guarantees that.

result.append(path[:]) records a copy of the current path at the top of each call, just like plain Subsets. Each node is a valid subset.

for i in range(start, len(nums)) loops over the numbers we may still pick. The start index keeps us from reusing earlier numbers.

if i > start and nums[i] == nums[i - 1]: continue is the duplicate skip. Read it carefully. The i > start part means we are not at the first choice of this level. The nums[i] == nums[i - 1] part means this value equals its left neighbour. When both are true, this is a repeated sibling, so we skip it. The very first equal value at a level still runs, because then i equals start. So we keep one copy and drop the rest.

path.append(nums[i]) chooses the number. backtrack(i + 1) explores deeper. path.pop() un-chooses, resetting the path for the next sibling.

⏱️ Time and Space Complexity

In the worst case, with all distinct numbers, there are still 2 to the power n subsets. So the time stays O(n times 2^n), same as plain Subsets. The sort adds O(n log n), which is small next to the exponential part. Duplicates only make the answer smaller, never bigger. The extra space is O(n) for the recursion depth and the path.

🧩 Key Takeaways

• ✅ Duplicates in the input can make the same subset appear twice.
• ✅ Sort first, so equal numbers become neighbours and are easy to skip.
• ✅ At each level, skip a value that equals its left neighbour when i > start.
• ✅ The first equal value at a level still runs, so you keep exactly one copy.
• ✅ Sorting is what makes the neighbour-based skip correct.

🚀 What’s Next?

• Combination Sum II
• Subsets