47. Permutations II

MediumBacktrackingDFS building full-length arrangements, pruning equal-value siblingsPermutation backtracking with used-array and duplicate skip

Permutations II

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

Open official problem prompt ↗

In plain English

Produce every distinct ordering of a multiset without listing the same ordering twice.

Picture it like this

Arranging labeled tiles in a row, except two tiles share the identical face; you agree to always place the leftmost unused identical tile first so mirror-image arrangements never get counted twice.

Example

Input: nums = [1,1,2]
Output: [[1,1,2],[1,2,1],[2,1,1]]
Why: These are the three distinct orderings of the multiset {1,1,2}; swapping the two identical 1s produces no new permutation.

Constraints

1 <= nums.length <= 8-10 <= nums[i] <= 10

Pattern lesson

See the pattern, then code

Permutation backtracking with used-array and duplicate skip

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. To avoid duplicates, fix a canonical order among equal values: an equal element may only be placed if its identical predecessor has already been placed in this branch, so equal items are consumed left to right.

New words, made simpleKnow these before the algorithm

used array: Boolean flags marking which positions are already placed in the current permutation.
Canonical duplicate order: The rule that an equal value may enter only after its identical predecessor, giving each permutation one representative.
Permutation: An arrangement using every element exactly once.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Permute then dedupe

Correct but explores and stores many duplicates unnecessarily.

Generate all n! orderings and drop repeats via a set of tuples.

Time O(n * n!)Space O(n!)

Best choiceSort + used[] + skip equal predecessor

Emits each unique permutation exactly once with no post filtering.

Sort, and skip nums[i] when it equals nums[i-1] and nums[i-1] is not used in this branch.

Time O(n * n!)Space O(n)

The rule we keep true

Invariant

Among any set of equal values, the ones already in the path always occupy an earlier-in-sorted-order set of positions, so each distinct permutation is generated by exactly one branch.

Why this is correct

Reasoning

The skip condition (nums[i]==nums[i-1] and not used[i-1]) forbids starting an equal value while its identical predecessor is still available, forcing left-to-right consumption of equal items. That gives every distinct arrangement a single canonical build path, eliminating duplicates while still reaching all of them.

The algorithm in three movesSay these aloud before coding

1Sort nums so equal values are adjacent

sorted=[1,1,2], used=[F,F,F]

2Track a used[] flag per position and build path

place nums[0]=1 -> used=[T,F,F], path=[1]

3When path length equals n, record a copy

next level: nums[1] allowed since nums[0] is used

4At each step skip an unused element equal to its predecessor whose predecessor is also unused

5Mark used, recurse, then unmark to explore other positions

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read[1,1,2]

2 · Askprepare

3 · Update stateused=[F,F,F], path=[]

4 · Resultstart recursion

Key takeaway

Sorted multiset [1,1,2]; identical 1s are consumed left to right to avoid duplicate permutations.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 2-5Sort and state
Sorting adjacency plus per-position used flags underpin the duplicate rule.
2
Lines 6-8Base case
A full-length path is a complete permutation; append a copy.
3
Lines 9-13Skip and guard
Skip already-used positions and equal siblings whose predecessor is unused.
4
Lines 14-19Choose and undo
Mark used, append, recurse, then restore both to try this position elsewhere.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

All elements identical, e.g. [2,2,2] -> a single permutation
All distinct -> full n! permutations
Single element -> one permutation

Common beginner mistakes

Using 'and used[i-1]' instead of 'and not used[i-1]', which flips the rule and drops valid permutations
Forgetting to sort, so equal values are not adjacent and the skip check misfires
Reusing the same position by not checking used[i]

Check your understanding

Why does the skip require nums[i-1] to be NOT used?

PyPython 3 · solution.py

Optimal

1class Solution:2    def permuteUnique(self, nums: list[int]) -> list[list[int]]:3        nums.sort()4        res: list[list[int]] = []5        path: list[int] = []6        used = [False] * len(nums)7        def backtrack() -> None:8            if len(path) == len(nums):9                res.append(path[:])10                return11            for i in range(len(nums)):12                if used[i]:13                    continue14                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:15                    continue16                used[i] = True17                path.append(nums[i])18                backtrack()19                path.pop()20                used[i] = False21        backtrack()22        return res

Time complexityO(n * n!) in the worst case to build and copy all permutationsOptimized

Space complexityO(n) for recursion, path, and used flags (excluding output)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftMeta

Permutations II

Permutations II

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking