Subsets II (with duplicates): sort then skip duplicates

• Subsets II – generate all unique subsets (the power set) from an array that may contain duplicates.
• Sort first – places equal values adjacent so duplicates can be detected by comparing neighbors.
• Skip guard – if (i > start && nums[i] == nums[i-1]) continue suppresses duplicate subsets at each decision level.
• i > start – allows the first occurrence to be chosen and recursed into, blocking only the second identical choice at the same level.
• Time – O(n * 2^n) worst case for all-distinct elements.

What is the Subsets II problem?

Given an array that may contain duplicates, return all unique subsets. For example, given [1, 2, 2], the unique subsets are [], [1], [2], [1,2], [2,2], [1,2,2]. Note that [2] appears once despite there being two 2s in the input.

package com.bank.dsa;

import java.util.List;

public interface SubsetGenerator {
    List<List<Integer>> subsetsWithDup(int[] nums);
}

Why sort the array first?

Sorting places equal values next to each other, which makes duplicate detection a simple adjacent-element comparison. Without sorting, you would need a set to track which values have been used at each level, which is more complex and uses more memory.

import java.util.Arrays;

int[] vouchers = {200, 100, 200};
Arrays.sort(vouchers);
// vouchers = [100, 200, 200]
// Now the two 200s are adjacent

How does the skip guard work?

Inside the backtracking loop at each level, the guard if (i > start && nums[i] == nums[i-1]) continue skips an element when its index is beyond the level's start and it equals the previous element. This prevents choosing the same value twice at the same decision level.

package com.bank.dsa;

import java.util.*;

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

    private static void backtrack(int[] nums, int start,
                                   List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path)); // record at every entry

        for (int i = start; i < nums.length; i++) {
            // Skip same-level duplicate
            if (i > start && nums[i] == nums[i - 1]) continue;

            path.add(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] vouchers = {200, 100, 200};
        List<List<Integer>> bundles = subsetsWithDup(vouchers);
        for (List<Integer> bundle : bundles) {
            System.out.println(bundle);
        }
    }
}

[]
[100]
[100, 200]
[100, 200, 200]
[200]
[200, 200]

Why is i > start the correct condition?

The condition i > start allows the first occurrence of a duplicate value at a level to be chosen and recursed into, where the duplicate can legitimately extend the path deeper. It blocks only a second identical choice at the same level, which would create a duplicate subset. If you used i > 0 instead, you would skip valid subsets that contain duplicates.

// Correct: i > start allows the first dup to be chosen
if (i > start && nums[i] == nums[i - 1]) continue;

// Wrong: i > 0 skips too aggressively
if (i > 0 && nums[i] == nums[i - 1]) continue;
// This would prevent [200, 200] from ever being generated

How does the recursion tree look with and without the skip?

Without the skip, the recursion tree generates duplicate subsets when choosing the second 200 at the same level as the first 200. With the skip, the second 200 at that level is pruned.

With skip (correct):
  Level 0: choose 100, choose 200 (first), skip 200 (second)
  Level 1 under 200: choose 200 (the second one, allowed deeper)

Without skip (wrong):
  Level 0: choose 100, choose 200 (first), choose 200 (second)
  --> [200] generated twice

What is the time complexity?

The worst case is when all elements are distinct: there are 2^n subsets, each taking O(n) to copy, so the total is O(n * 2^n). When duplicates are present, branches are pruned, reducing the actual work. The space is O(n) for the recursion stack and the current path.

All distinct: 2^n subsets, O(n) copy each = O(n * 2^n)
With duplicates: fewer subsets due to pruning
Recursion depth: O(n)

Where else does this pattern appear?

The same skip-same-level-duplicate pattern reappears in Combination Sum II (skip duplicate candidates) and Permutations II (skip unused equal predecessors). Recognising it as one reusable technique across three problems saves re-deriving it each time.

| Problem | Skip Condition | Extra Rule |
|---|---|---|
| Subsets II | i > start && nums[i] == nums[i-1] | Record at every entry |
| Combination Sum II | i > start && cand[i] == cand[i-1] | Recurse with i+1 (use once) |
| Permutations II | !used[i-1] && nums[i] == nums[i-1] | Canonical left-to-right order |

What are common mistakes?

The most common mistake is using i > 0 instead of i > start, which over-skips and misses valid subsets. Another is forgetting to sort the array first, which makes the skip guard ineffective because duplicates may not be adjacent.

// Wrong: forgot to sort
int[] nums = {2, 1, 2};
// nums[1]=1, nums[2]=2, so nums[2] != nums[1]
// Skip guard never fires, duplicates leak through

// Correct: sort first
Arrays.sort(nums); // [1, 2, 2]
// Now nums[2] == nums[1], skip guard works

What should a senior engineer know?

A senior engineer recognises this as the general "skip same-level duplicates" idiom, sorts first to make duplicates adjacent, and knows that the i > start condition is what distinguishes "already used deeper" from "duplicate at this level". They mention the cross-problem pattern and can code it from memory.