Problem Statement

Permutations II

You are given a list of numbers, and some of them might be the same. A permutation is just one way to line all the numbers up in a row. We want every possible lineup, but with no repeats. For example, if two of the numbers are both 1, swapping those two 1s gives the exact same row, so we should count that row only once. The plan: sort the numbers first so equal ones sit next to each other, keep a small checklist of which numbers we have already placed in the current row, and use one simple rule to skip the copies that would create a repeat lineup.

mediumBacktrackingBacktrackingTime: O(n * n!) · Space: O(n)

Signals to notice

all unique permutations from array with duplicatesskip same-value at same levelsort + used array

Brute force first

Generate all, deduplicate — O(n! × n).

The key insight

Sort. Backtrack with used array. Skip nums[i] if nums[i] == nums[i-1] and !used[i-1]. O(n! / duplicates).

Trace it on `nums=[1,1,2]`

sort -> [1,1,2]; used=[F,F,F], path=[], result=[]
i0 pick 1: used=[T,F,F], path=[1] -> recurse
i1 pick 1 (used[0]=T, allowed): used=[T,T,F], path=[1,1]; i2 pick 2 -> path=[1,1,2] full -> record [1,1,2]
unwind to path=[1]; i2 pick 2 -> [1,2]; i1 pick 1 -> [1,2,1] full -> record [1,2,1]
unwind to path=[]; i1=1: nums[1]==nums[0] and used[0]=F -> SKIP duplicate
i2 pick 2: path=[2]; i0 pick 1 -> [2,1]; i1 pick 1 -> [2,1,1] full -> record [2,1,1]
all branches done -> return [[1,1,2],[1,2,1],[2,1,1]]

What must stay true

Identical values are forced into left-to-right usage order — prevents generating the same permutation via different copies.

Shape of the loop

sort(nums); used = [false]*n
backtrack(path):
  if len(path)==n: record(copy(path)); return
  for i in 0..n-1:
    if used[i]: continue
    if i>0 and nums[i]==nums[i-1] and not used[i-1]: continue   # skip dup
    used[i]=true; path.push(nums[i]); backtrack(path); path.pop(); used[i]=false

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

The skip condition: skip if nums[i] == nums[i-1] AND !used[i-1]. This forces identical values to be used in order.

Backtracking Pattern