Permutations II: Backtracking with Duplicate Handling

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

This is LeetCode 47: Permutations II, and it builds directly on Permutations. The twist is that nums can contain duplicate values (like [1, 1, 2]), and the result must not contain duplicate permutations. Without careful handling, the standard backtracking approach generates repeated results. The fix is sorting the input, using a used boolean array, and adding a single guard clause that skips same-level duplicates.

Why this problem matters

Permutations II teaches you how to handle duplicates in a permutation context. In Permutations, all elements are distinct, so every arrangement is unique by default. Once duplicates enter the picture, you need a pruning strategy. The technique here is the same one you use in Combination Sum II and Subsets II: sort the input, then skip a value if it equals its predecessor and that predecessor has not been used. Learning it once in one context makes it automatic in all of them.

This problem also reinforces the used-array approach to backtracking. In Permutations, the swap-based method is elegant, but adapting it for duplicate skipping is error-prone. The used-array version makes the skip condition clean and predictable. When an interviewer asks for permutations with duplicates, reaching for the used-array approach is the safer choice.

The key insight

Sort nums first. Then, when iterating over choices at a given recursion level, skip nums[i] if it equals nums[i - 1] and used[i - 1] is False.

Why does used[i - 1] == False matter? Consider sorted input [1, 1, 2]. At the root level, you pick the first 1 (index 0) and explore all permutations starting with that 1. When you backtrack and reach the second 1 (index 1), used[0] is False because you already un-chose it. That means the first 1 was available at this level but you already fully explored it. Picking the second 1 at the same level would produce the exact same subtree, so you skip it.

At a deeper level, the situation is different. If you have already picked nums[0] = 1 and you are now considering nums[1] = 1, then used[0] is True. The skip condition does not trigger, and you correctly allow both 1s in the same permutation (like [1, 1, 2]).

The algorithm:

1. Sort nums.
2. Initialize a used boolean array of length n, all False.
3. Backtrack: if the current path has length n, record it.
4. For each index i from 0 to n-1:
   • If used[i], skip (element already in the current path).
   • If i > 0 and nums[i] == nums[i - 1] and not used[i - 1], skip (same-level duplicate).
   • Otherwise, mark used[i] = True, append nums[i] to the path, recurse, then pop and mark used[i] = False.

The backtracking solution

def permuteUnique(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            result.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 result

The outer function sorts nums and sets up the used array. Sorting groups identical values together so they can be detected by comparing adjacent elements.

Inside backtrack, the base case checks whether the path length equals n. When it does, you have a complete permutation. Copy it with path[:] and add it to the result.

The for loop iterates over all indices. Two guard clauses appear before the choose step.

First, if used[i] is True, this element is already part of the current path. Skip it.

Second, if i > 0 and nums[i] == nums[i - 1] and not used[i - 1], this is a same-level duplicate. The condition not used[i - 1] means the previous identical element is not in the current path. It was tried at this same recursion level and then un-chosen, which means its entire subtree has already been explored. Picking nums[i] here would duplicate that work, so skip it.

After the guards, you choose (mark used, append), explore (recurse), and unchoose (pop, unmark). This is the standard choose-explore-unchoose template.

Visual walkthrough

Let's trace through the algorithm with nums = [1, 1, 2]. After sorting, the array stays [1, 1, 2]. Watch how the skip condition prevents the second 1 from duplicating work at the root level.

The key moment is Step 5. When the loop reaches i=1 at the root level, nums[1] == nums[0] (both are 1) and used[0] is False. The skip condition fires, and the entire subtree that would start with the second 1 at position 0 is pruned. This subtree would have produced [1, 1, 2] and [1, 2, 1] again, which are already in the result.

Notice that [1, 1, 2] is still valid. The two 1s in that permutation come from different recursion levels: nums[0] is picked at the root level, and nums[1] is picked one level deeper (where used[0] is True, so the skip condition does not trigger).

Complexity analysis

Time is O(n * n!) in the worst case (all elements distinct). When duplicates exist, the actual number of unique permutations is n! / (k1! * k2! * ... * km!) where ki is the count of each distinct value. Sorting adds O(n log n), dominated by the factorial term. Each permutation takes O(n) to copy.

Space is O(n) for the used array, the recursion stack (maximum depth n), and the current path. The output itself holds all unique permutations, but if you exclude the output, extra space is O(n).

The building blocks

This problem is built on two core reusable pieces that CodeBricks drills independently.

Permutation backtracking (used-array template)

The same skeleton from Permutations, using a used boolean array to track which elements are in the current path:

def backtrack(path):
    if len(path) == len(nums):
        result.append(path[:])
        return

    for i in range(len(nums)):
        if used[i]:
            continue
        used[i] = True
        path.append(nums[i])
        backtrack(path)
        path.pop()
        used[i] = False

This template generates all n! permutations when all elements are distinct. The loop tries every unused element at each position. The used array prevents reuse within a single permutation.

Same-level duplicate skipping

The pattern for avoiding duplicate results when the input contains repeated values:

if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
    continue

This guard appears in any backtracking problem where the input has duplicates and the output must be unique. The same technique applies to Combination Sum II (LeetCode 40) and Subsets II (LeetCode 90). In the Permutations context, not used[i - 1] ensures you only skip when the identical predecessor was available at this level but already explored. If the predecessor is currently used (in the path), you are at a deeper level, and both copies are legitimately part of the same permutation.

Edge cases

Before submitting, check these:

• All elements the same: nums = [1, 1, 1]. Should return [[1, 1, 1]]. Only one unique permutation exists. The skip condition prunes every duplicate branch.
• No duplicates: nums = [1, 2, 3]. Should return all 6 permutations. The skip condition never triggers because no adjacent elements are equal after sorting. Behaves identically to Permutations I.
• Two elements: nums = [1, 1]. Should return [[1, 1]]. Only one unique permutation. Good sanity check that the skip logic works at the smallest duplicate case.

From understanding to recall

You understand the recursion tree. You see how sorting groups duplicates, how the used array tracks what is in the current path, and how not used[i - 1] distinguishes same-level duplicates from deeper-level reuse. But can you write the solution from scratch in under two minutes?

That is what interviews demand. The duplicate-skipping guard is easy to get wrong under pressure. Checking used[i - 1] instead of not used[i - 1], forgetting to sort, or confusing the used-array approach with the swap approach are all common mistakes. These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the permutation backtracking template and the same-level duplicate-skipping guard from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "permutations with duplicates" and the code flows out without hesitation.

The permutation backtracking and same-level duplicate skipping patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Permutations - The version with distinct elements. Compare the two to see how sorting and the not used[i - 1] guard adapt the same template for duplicates.
• Combination Sum II - Uses the same same-level duplicate skipping technique in a combination context. The skip condition is i > start and candidates[i] == candidates[i - 1], which is the combination-flavored equivalent of the not used[i - 1] check here.

CodeBricks breaks Permutations II into its permutation-backtracking and duplicate-skipping building blocks, then drills them independently with spaced repetition. You type the backtracking skeleton and the deduplication guard from scratch until they are automatic. When a backtracking-with-duplicates problem shows up in your interview, you do not think about it. You just write it.