intermediate9 min read·Updated October 3, 2026

Subsets with Duplicates Explained: Unique Subsets of [1, 2, 2]

Master generating subsets with duplicates using a sorting and skipping mental model. Walk through [1, 2, 2] step-by-step to avoid duplicate combinations.

By Learnisim AI·Published October 3, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic recursion
  • Standard subset generation (power set)
  • Array sorting concepts
Unique Subsets of [1, 2, 2] & The Sibling-Skip Rule 1. Input & Sorted Array nums[0]:1 nums[1]:2 nums[2]:2 Sorted: adjacent duplicates sit side-by-side 2. The Duplicate Collision Naive power-set creates duplicates: • Pick 1st '2' → [1, 2] • Pick 2nd '2' → [1, 2] (Redundant!) Goal: Exactly 6 unique valid subsets 3. The Sibling-Skip Rule if (i > start && nums[i] == nums[i-1]) continue; Skips duplicate branches at the same recursion level 4. Backtracking Decision Tree & Unique Subsets Discovery [ ] (Start) [1] [2] [2] (SKIPPED duplicate) [1, 2] [1, 2] (SKIPPED) [1, 2, 2] [2, 2] All 6 Unique Subsets Output: [ ], [1], [2], [1, 2], [2, 2], [1, 2, 2] ★ Exact structural uniqueness guaranteed
Unique subsets of [1, 2, 2] overview diagram
Why

Why Duplicates Break Simple Subset Generation

Phase 1: The Duplicate Collision Problem

Imagine you are asked to find every possible combination of elements from the array nums = [1, 2, 2]. In standard subset problems where all numbers are distinct, a set of size always yields exactly subsets. For our given array, that formula would predict subsets. But pause and look closely at the elements: you have two distinct 2 values.
If you blindly treat every position as independent, you will generate duplicate subsets like twice—once by picking the first 2 and once by picking the second 2. Downstream systems or tests will fail if your final collection contains redundant answers like [[1, 2], [1, 2]]. We need a strategy that acknowledges the values rather than their index positions, ensuring that identical combinations are never produced twice.

The Core Challenge

Given the array nums = [1, 2, 2], how do we systematically avoid redundant branches while still discovering all six valid unique subsets: ?
Why Duplicates Break Simple Subset Generation ([1, 2, 2]) Naive index-based recursion creates redundant [1, 2] branches. Sorting + skipping duplicates fixes it. Naive Tree (8 branches: 2^3) [ ] [1] [ ] [1, 2a] [1] [1, 2a, 2b] [1, 2a] [1, 2b] Collision Alert: Redundant Results Both [1, 2a] and [1, 2b] evaluate to the exact same subset value: [1, 2] (Duplicated!) Sorted Strategy (Skip Adjacent Duplicates) The Fix: if (i > start && nums[i] == nums[i-1]) continue; Forbids picking duplicate values at the same recursion depth. Exactly 6 Unique Valid Subsets Generated: [ ] [1] [1, 2] [1, 2, 2] [2] [2, 2] Why This Works Seamlessly 1. Sorting groups identical values adjacent to each other. 2. Skipping duplicate recursive branch entry prunes redundant paths entirely, keeping exact unique combinations.
Why Duplicates Break Simple Subset Generation diagram
Model

The Sorting and Skipping Model for Unique Subsets

Phase 2: The Mental Model

When generating the subsets for nums = [1, 2, 2], naive approaches like the power set bitmask method or a standard backtracking inclusion-exclusion tree will blindly generate duplicate branches. If we treat the two 2s as distinct positions in memory, we will end up producing [1, 2] twice. To eliminate these redundant branches before they occur, we need a spatial model: sorting the array first, followed by a strict sibling-skip rule.
Imagine our backtracking algorithm building subsets level by level. At any given index in our recursion, we loop through the remaining elements to pick our next inclusion. If we encounter a value that matches the element we just processed at the same recursion depth, we skip it. Why? Because any subset formed by choosing the second 2 without the first 2 would be an exact structural duplicate of a branch we already explored.

The Sibling-Skip Rule

For our locked example [1, 2, 2], sorting produces the identical array [1, 2, 2]. When our decision tree branches from the root [], it considers taking 1, or taking the first 2, or taking the second 2.
Sorted input: [1, 2, 2]
Level 0: []
├── Take 1 -> [1]
│ ├── Take first 2 -> [1, 2]
│ │ └── Take second 2 -> [1, 2, 2]
│ └── Take second 2 (SKIPPED because second 2 == first 2 at same level)
├── Take first 2 -> [2]
│ └── Take second 2 -> [2, 2]
└── Take second 2 (SKIPPED because second 2 == first 2 at same level)
By enforcing if i > start and nums[i] == nums[i - 1], we ensure that duplicate values are only ever chained sequentially rather than chosen as alternative starting points for the same subset size at the same tree depth.
Try this: Given nums = [1, 2, 2], explain in your own words why checking nums[i] == nums[i-1] alone (without the i > start condition) would incorrectly prevent the generation of the valid subset [2, 2].
The Sorting & Skipping Model for Unique Subsets — [1, 2, 2] Step 1: Sort Input 1 2ₐ 2ᵦ if i > start and nums[i] == nums[i-1]: ↳ SKIP duplicate sibling branch! Why (i > start) is Crucial • Without i > start, checking only nums[i] == nums[i-1] would block taking [2, 2] at deeper recursion levels! Allows sequential pick: [2] → [2,2] Blocks parallel duplicate: Skip picking 2ᵦ without 2ₐ Recursion Decision Tree & Sibling Skips [ ] Take 1 Take 2ₐ Take 2ᵦ [1] [2ₐ] SKIPPED (Duplicate) Take 2ₐ Take 2ᵦ Take 2ᵦ [1, 2] SKIPPED (nums[i]==nums[i-1]) [2, 2] Take 2ᵦ [1, 2, 2] Final Deduped Unique Subsets Result Set: [ ], [1], [1, 2], [1, 2, 2], [2], [2, 2]
The Sorting and Skipping Model for Unique Subsets diagram
Worked example

Tracing the Algorithm for Unique Subsets of [1, 2, 2]

Phase 3: Walking Through the Backtracking Tree

Let us trace our locked example: finding all unique subsets for nums = [1, 2, 2] using the sorting and skipping model. Because the array is already sorted, duplicate values like 2 and 2 sit adjacent to each other. We will track our recursion state using a path array (the current subset being built) and an index pointer representing our start position for the next choice.

Given

- Input: nums = [1, 2, 2]
- Sorted input: [1, 2, 2] ()
- Expected output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

Steps

1. Start at index 0 with an empty path []: Record [] to our results list. We branch out to consider elements starting at index 0.
2. Choose index 0 (val = 1): Path becomes [1]. Record [1]. Recurse to index 1.
- At index 1, choose val = 2. Path becomes [1, 2]. Record [1, 2]. Recurse to index 2.
- At index 2, choose val = 2. Path becomes [1, 2, 2]. Record [1, 2, 2]. Recurse to index 3 (base case, return).
- Unchoose second 2, return to index 1 branch.
3. Backtrack to index 0 level, choose index 1 (val = 2): Path becomes [2]. Record [2]. Recurse to index 2.
- At index 2, we consider nums[2] = 2. Notice that index () and nums[2] == nums[1] (). The skip condition triggers! We skip this duplicate branch entirely.
4. Backtrack to index 0 level, evaluate index 2 (val = 2): Since index () and nums[2] == nums[1], the skip condition triggers again at the root level! We skip this branch, preventing the duplicate subset [2] from being generated a second time.

Result

Collecting all recorded states yields exactly six unique subsets:
json
[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
python
def subsetsWithDup(nums):
    nums.sort()
    result = []
    
    def backtrack(start, path):
        result.append(list(path))
        for i in range(start, len(nums)):
            # FILL IN THE MISSING SKIP CONDITION HERE
            if _________:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
            
    backtrack(0, [])
    return result
Tracing Backtracking Tree for nums = [1, 2, 2] Focusing on index choice, path progression, and the duplicate skip condition Sorted Input: [1, 2, 2] Skip Rule: i > start and nums[i] == nums[i-1] start=0 | [] choose 1 (i=0) skip 2 (i=2 > start) start=1 | [1] SKIP (i=2, nums[2]==nums[1]) choose 2 (i=1) start=2 | [1, 2] choose 2 (i=2) start=3 | [1, 2, 2] Why the Skip Condition Works: • Adjacent duplicates like [2, 2] are sorted. • Skipping duplicate elements when i > start prevents generating identical branches twice.
Tracing the Algorithm for Unique Subsets of [1, 2, 2] diagram
Practice

Predicting the Subset Tree for a Modified Duplicate Array

Phase 4: Practice

Now that you have traced the exact mechanics for nums = [1, 2, 2], it is time to test your understanding on a variation of the same problem. Let us shift our input slightly to nums = [2, 2, 3] and track how the sorting and skipping rules constrain the decision tree.
Following the model from earlier, the algorithm first sorts the array, though [2, 2, 3] is already in non-decreasing order. At the root, we can choose the first 2, the second 2, or 3. The core skipping condition states that if i > start and nums[i] == nums[i-1], we skip the iteration to prevent generating duplicate branches.
Take a moment to mentally construct the recursion tree or trace the backtracking steps for nums = [2, 2, 3]. How many unique subsets will be produced, and what happens when the algorithm encounters the second 2 at the top level of recursion?
python
def subsetsWithDup(nums: list[int]) -> list[list[int]]:
    # Given nums = [2, 2, 3]
    # Predict the final list of unique subsets and trace why [2] (using the second 2) is skipped when the first 2 is not chosen.
    pass
Apply

Transferring Subset Deduplication to Partition and Combination Problems

Phase 5: Transfer

Now that you have mastered generating unique subsets of [1, 2, 2] using sorting and index-based deduplication, you possess a structural pattern that reappears across combinatorial search. The exact rule—sort first, then skip duplicates among siblings at the same recursion depth—is not restricted to power sets. It solves any backtracking problem where order does not matter and input elements repeat.
Consider how this applies to finding combinations that sum to a target value, such as finding all combinations of [1, 2, 2, 5] that sum to 5. Without the duplicate-skipping mechanism learned from our [1, 2, 2] trace, your recursion tree would evaluate redundant branches for the identical 2 elements at the same tree level. By applying the check if i > start and nums[i] == nums[i-1]: continue, you eliminate whole clusters of redundant work instantly.
python
# General template for any duplicate-sensitive combination or subset search:
def backtrack(start, path, target):
    if target == 0:
        result.append(list(path))
        return
    for i in range(start, len(nums)):
        if i > start and nums[i] == nums[i-1]:
            continue
        if nums[i] > target:
            break # if array is sorted
        path.append(nums[i])
        backtrack(i + 1, path, target - nums[i])
        path.pop()
This same logic governs partition problems, word break variations, and multi-set permutations with minor adjustments to the indexing. Whenever you see a backtracking prompt where duplicate items threaten to flood your output with indistinguishable answers, remember the twin pillars: sort to cluster equals, skip siblings to enforce uniqueness.
python
QUESTION: You are given a modified input array nums = [2, 2, 3, 5] to find all unique combinations summing to 5. Explain how the sibling-skip condition (i > start and nums[i] == nums[i-1]) prevents the algorithm from generating duplicate combination paths when multiple 2s are available at the initial decision root.

FAQ

Why does the standard subset algorithm produce duplicate subsets for [1, 2, 2]?
The standard power set algorithm treats identical values at different indices as distinct choices. For [1, 2, 2], it generates the subset [1, 2] twice—once using the first '2' and once using the second '2'.
How does sorting help eliminate duplicate subsets?
Sorting groups identical elements together. This allows the backtracking algorithm to enforce a strict rule: if an element is a duplicate of its predecessor and the predecessor wasn't chosen in the current recursive branch, skip it to prevent generating identical subset branches.
What is the time complexity of generating subsets with duplicates?
The time complexity is O(n * 2^n) in the worst case, where n is the length of the array, because there can be up to 2^n subsets and each subset takes O(n) time to construct and copy.
Does the order of elements in the input array matter?
Yes. The algorithm relies on sorting the array first so that duplicate values are adjacent. Without sorting, the skipping condition cannot reliably detect and suppress duplicate branches.

Keep learning