intermediate9 min read·Updated October 3, 2026

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

Master permutations with duplicates using the twin-skipping mental model. Follow a complete trace of [1, 1, 2] to avoid duplicate branches and master backtracking.

By Learnisim AI·Published October 3, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic recursion
  • Standard backtracking permutations
Unique Permutations of [1, 1, 2] — Twin-Skipping Algorithm 1. Sorted Input & The Trap 1_A (idx 0) 1_B (idx 1) 2 (idx 2) Standard perms create 6 outputs (3 redundant) 2. The Twin-Skipping Invariant if nums[i] == nums[i - 1] and not used[i - 1]: → SKIP this branch! Prevents identical twin swapping order Why it works: Forces identical items to be picked in strict left-to-right order index-wise, eliminating duplicate mirror branches. Result: exactly 3 unique permutations 3. Backtracking Decision Tree & Execution Trace [] (root) path: [1_A] pick idx 0 skip 1_B Rule triggers! path: [1, 1] path: [1, 2] [1, 1, 2] ✓ [1, 2, 1] ✓ path: [2] [2, 1, 1] ✓ Final Output Set: { [1, 1, 2], [1, 2, 1], [2, 1, 1] } Zero redundant branches explored — optimal O(N!) time with pruning
Unique permutations of [1, 1, 2] overview diagram
Why

Why Standard Permutations Fail on Duplicate Elements

Phase 1: The Trap of Identical Items

Imagine you are handed the array nums = [1, 1, 2] and asked to generate every unique arrangement. If you treat every element position as completely distinct—as a standard backtracking permutation algorithm does—you end up generating six outcomes instead of the correct three: , , , , , and . Notice how the identical 1s swap places in the background, creating invisible duplicate work that clutters your final output. Without a specialized strategy for handling duplicate values, your code wastes precious time exploring redundant paths and forces you to build expensive post-processing filters just to strip out the duplicates later.
Why Standard Permutations Fail on Duplicate Elements: nums = [1₁, 1₂, 2] Naive Backtracking (Treats Index as Unique) Root [] [1₁] [1₂] (Dup) [2] [1₁, 1₂] [1₁, 2] [1₁, 1₂, 2] [1₁, 2, 1₂] Generates 6 permutations instead of 3! Swapping identical 1s creates redundant branches Fix Rule Smart Backtracking (Pruning Duplicates) Root [] pick '1' pick '2' Skip identical [1, 1] [1, 2] [1, 1, 2] [1, 2, 1] [2, 1, 1] Exactly 3 Unique Permutations! Skip if nums[i] == nums[i-1] and previous not used
Why Standard Permutations Fail on Duplicate Elements diagram
Model

The Twin-Skipping Mental Model for Unique Permutations

Phase 2: The Model

To tame duplicate elements in nums = [1, 1, 2], we need a mental model that prevents identical branches from spawning in our backtracking tree. If we treat the two ones as identical objects, standard permutation algorithms blindly swap them in different orders, producing redundant clones of [1, 1, 2].
Instead, picture the backtracking process as picking numbers one by one from a sorted row. If we encounter identical adjacent numbers, we establish a strict rule: a duplicate number can only be chosen if its identical twin has already been chosen in the current branch.
Let us map this to our locked example where nums = [1, 1, 2]. The sorted order keeps twins side by side. When deciding whether to place the second 1 at a particular slot, we check if the first 1 (its left neighbor) was used in the current path. If the first 1 is still unused, it means we bypassed it or it was just released, signaling that picking the second 1 right now would create a redundant mirror path.
Sorted input: [1_A, 1_B, 2]
Decision tree rule:
If nums[i] == nums[i - 1] AND used[i - 1] is FALSE:
SKIP this branch!
This single invariant turns a chaotic, redundant search space into a clean, deterministic tree that yields our exact target of three unique permutations: .
python
def backtrack(nums, used, path, result):
    # TODO: implement the duplicate-skipping check here
    pass
The Twin-Skipping Mental Model for Unique Permutations ([1, 1, 2]) 1. Sorted Input with Distinct Twin Tags 1_A 1_B 2 Twins kept side by side 2. The Strict Twin-Skipping Invariant If nums[i] == nums[i-1] AND used[i-1] is FALSE: SKIP THIS BRANCH! (Prevents duplicate clones) 3. Deterministic Backtracking Decision Tree for [1_A, 1_B, 2] [] (Root) pick 1_A pick 1_B (SKIP!) pick 2 [1_A] [1_B] pruned [2] pick 1_B pick 2 [1_A, 1_B] [1_A, 2] [1, 1, 2] ✓ [1, 2, 1] ✓ pick 1_A, 1_B [2, 1, 1] ✓ Exact Result: {[1,1,2], [1,2,1], [2,1,1]}
The Twin-Skipping Mental Model for Unique Permutations diagram
Worked example

Tracing the Decision Tree for Permutations with Duplicates

Phase 3: Stepping Through the Algorithm

Let us trace our locked example: finding the unique permutations of nums = [1, 1, 2]. Following the mental model established previously, we sort the array first so that identical elements sit adjacent to one another. We maintain a path array to build our current permutation, and a boolean used array to track which indices are already included.

Given

- nums = [1, 1, 2] (already sorted)
- used = [false, false, false]
- path = []

Steps

1. First position choices: We can pick index 0 (the first 1). path = [1], used = [true, false, false].
2. Second position choices: From remaining indices 1 and 2, we can pick index 1 (the second 1). path = [1, 1], used = [true, true, false].
- Then for the third position, we pick index 2 (2). path = [1, 1, 2], used = [true, true, true]. We record our first valid result: [1, 1, 2].
3. Backtracking and duplicate avoidance: We backtrack to path = [1], used = [true, false, false]. Now we consider picking index 1 (the second 1) for the second position. However, our twin-skipping rule checks: nums[1] == nums[0] and used[0] is false (meaning the previous twin was not used in this branch). The rule triggers! We skip index 1, avoiding a duplicate branch that would mirror step 2.
4. Continuing the branch: Instead, we pick index 2 (2) for the second position. path = [1, 2], used = [true, false, true]. For the third position, the only remaining unused element is index 1 (1). path = [1, 2, 1], used = [true, true, true]. We record our second valid result: [1, 2, 1].
5. Starting with the two: Backtrack completely and pick index 2 (2) for the first position. path = [2], used = [false, false, true]. For the second position, we can pick the first 1 (index 0). path = [2, 1], used = [true, false, true]. For the third position, we pick the second 1 (index 1). path = [2, 1, 1], used = [true, true, true]. We record our third valid result: [2, 1, 1].

Result

The backtracking algorithm terminates having generated exactly three unique permutations: [[1,1,2], [1,2,1], [2,1,1]].
python
# Intermediate state trace for nums = [1, 1, 2]
# Path: [1] -> [1, 1] -> [1, 1, 2]  (Result 1)
# Path: [1] -> [1, 2] -> [1, 2, 1]  (Result 2)
# Path: [2] -> [2, 1] -> [2, 1, 1]  (Result 3)
Try this: Explain what happens when the backtracking algorithm considers index 1 of nums = [1, 1, 2] right after abandoning index 0 at the root level.
Phase 3: Tracing Decision Tree for [1, 1, 2] Path building, twin-skipping, and final unique permutations Sorted Input: nums = [1, 1, 2] Indices: [0]=1, [1]=1, [2]=2 Pick Index 0 (first 1) path = [1] Pick Index 1 (second 1) path = [1, 1] Result 1: [1, 1, 2] Index 2 (2) completes path Backtrack Skip Index 1 (Twin-skip rule) nums[1]==nums[0] & used[0]==false Avoids duplicate branch! Pick Index 2 (2) path = [1, 2] used[2] = true Result 2: [1, 2, 1] Pick remaining Index 1 (1) path = [1, 2, 1] Final Branch (Start with 2): Pick index 2 first -> path = [2] -> [2, 1] -> Result 3: [2, 1, 1] Algorithm Output: Generated exactly 3 unique permutations: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
Tracing the Decision Tree for Permutations with Duplicates diagram
Practice

Predicting the Path for a Modified Duplicate Array

Phase 4: Practice Your Twin-Skipping Intuition

Now that we have traced the exact branches for the base array , let us see how the logic holds up when we shift one duplicate. Consider a new input list: . Our goal is to find all unique permutations without generating redundant clones.
Recall our core deduplication rule from the previous steps: after sorting the array, if we encounter a duplicate element where , we must skip it unless the preceding twin has already been used in the current branch. Apply this exact rule mentally to construct the first two valid branches for .
python
# Starter prompt for your mental trace or scratchpad:
nums = [1, 2, 2]
# Sorted: [1, 2, 2]
# Index 0: value 1
# Index 1: value 2 (first twin)
# Index 2: value 2 (second twin)
Work through the recursive tree by deciding what happens when the algorithm hits the second 2 while the first 2 is still marked unused. Use the question below to verify your mental model against the expected output.
python
nums = [1, 2, 2]
# Question: How many total unique permutations will be generated for [1, 2, 2], and what is the exact second permutation produced after [1, 2, 2]?
Apply

Scaling the Twin-Skipping Rule to General Duplicate Arrays

Phase 5: Applying the Pattern to New Inputs

We started our journey with and successfully constrained our backtracking tree to produce exactly 3 unique permutations: . The core engine we built—sorting the input and applying the twin-skipping rule nums[i] == nums[i-1] and not used[i-1]—was specifically designed to prevent identical branches from spawning.
Now, let's take this exact mental model and transfer it to a more complex structure. Imagine you are given an array with two distinct pairs, such as , which sorts to . When your backtracking algorithm encounters the second 1 while the first 1 is unused, the twin-skipping rule immediately halts that branch before any recursion occurs. This guarantees that your time complexity remains proportional to the number of unique arrangements rather than the bloated factor.
By anchoring your understanding to our initial walkthrough of , you can now solve any permutation problem involving duplicate elements—whether it is strings with repeating characters or inventory lists with interchangeable items. The sorting and the adjacency check form a universal shield against redundancy.
python
def permuteUnique(nums):
    nums.sort()
    res = []
    used = [False] * len(nums)
    
    def backtrack(path):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False
            
    backtrack([])
    return res

FAQ

Why does standard permutation fail when an array contains duplicates?
Standard permutation algorithms treat identical values at different index positions as distinct elements. For an array like [1, 1, 2], this results in 6 permutations instead of the 3 truly unique ones because swapped identical digits generate redundant branches.
How many unique permutations does [1, 1, 2] produce?
The array [1, 1, 2] produces exactly 3 unique permutations: [1,1,2], [1,2,1], and [2,1,1].
What is the twin-skipping rule in backtracking?
The twin-skipping rule dictates that when sorting an array with duplicates, if the current element is equal to the previous element and the previous element has not been used in the current branch, we skip the current element to avoid duplicate permutations.
What is the time complexity of generating permutations with duplicates?
The time complexity is bounded by O(N * N!), where N is the number of elements. However, duplicate skipping prunes redundant branches significantly, reducing the actual number of operations in practice.

Keep learning