DSA Tracker

Visualize

Permutations II

Sorted input, used[] flags, skip a duplicate whose left twin is unused

time O(n * n!)space O(n) recursion and flags, beyond the output

Ordinary permutation backtracking treats the two 1s as different objects, so it builds each ordering twice and only a set at the end can tell. Sorting first puts equal values next to each other, and then one rule prunes the duplicates before they are built: a value may be placed only if it is not equal to its left neighbour, or that neighbour is already in the current path. Each group of equal values is therefore consumed strictly left to right, which picks exactly one of the interchangeable branches and discards the rest at the cost of a single comparison. The displayed array is the sorted input; used cells are shaded, the candidate being decided is marked, and a rejected duplicate is crossed off.

Details

Animated on: nums = [1, 1, 2], which contains a duplicate. Return every unique permutation. Answer: [1, 1, 2], [1, 2, 1], [2, 1, 1].

Problem:Permutations IIMedium

Pattern:Backtracking Basics

Sorted input, used[] flags, skip a duplicate whose left twin is unused

step 1 / 15

1
[0]
1
[1]
2
[2]

Input [1, 1, 2] is sorted to [1, 1, 2] so that equal values sit side by side. That adjacency is what lets one comparison, nums[i] = nums[i-1], detect a duplicate choice instead of remembering every value tried at this depth. Path is empty; every cell is still available.

  • depth=0· arr[0] = 1
Pseudocode
1FUNCTION permuteUnique(nums)
2  SORT nums
3  FUNCTION backtrack(path, used)
4    IF LENGTH(path) = LENGTH(nums)
5      APPEND COPY(path) TO out
6      RETURN
7    FOR i <- 0 TO LENGTH(nums) - 1
8      IF used[i] OR (i > 0 AND nums[i] = nums[i-1] AND NOT used[i-1])
9        CONTINUE
10      used[i] <- TRUE, APPEND nums[i] TO path
11      backtrack(path, used)
12      used[i] <- FALSE, REMOVE LAST FROM path
13  backtrack(EMPTY LIST, ALL FALSE)
14  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. Input [1, 1, 2] is sorted to [1, 1, 2] so that equal values sit side by side. That adjacency is what lets one comparison, nums[i] = nums[i-1], detect a duplicate choice instead of remembering every value tried at this depth. Path is empty; every cell is still available.
  2. Place nums[0]=1 at depth 0: path becomes [1], used[0] <- TRUE. Recurse to fill the next slot from the cells still unused.
  3. Place nums[1]=1 at depth 1: path becomes [1, 1], used[1] <- TRUE. Its twin nums[0] is already in the path, so this duplicate is allowed. Recurse to fill the next slot from the cells still unused.
  4. Place nums[2]=2 at depth 2: path becomes [1, 1, 2], used[2] <- TRUE. Recurse to fill the next slot from the cells still unused.
  5. All 3 cells are used, so the path [1, 1, 2] is a complete permutation. Record a copy: 1 found so far. Now unwind one level and give that slot its next candidate.
  6. Place nums[2]=2 at depth 1: path becomes [1, 2], used[2] <- TRUE. Recurse to fill the next slot from the cells still unused.
  7. Place nums[1]=1 at depth 2: path becomes [1, 2, 1], used[1] <- TRUE. Its twin nums[0] is already in the path, so this duplicate is allowed. Recurse to fill the next slot from the cells still unused.
  8. All 3 cells are used, so the path [1, 2, 1] is a complete permutation. Record a copy: 2 found so far. Now unwind one level and give that slot its next candidate.
  9. Skip nums[1]=1: it equals nums[0]=1, and that twin is NOT in the path. Whatever this branch would build, the branch that started with nums[0] already built the same ordering, since the two 1s are indistinguishable. Placing a duplicate is only allowed after its left twin is placed, so each group of equals is consumed left to right exactly once.
  10. Place nums[2]=2 at depth 0: path becomes [2], used[2] <- TRUE. Recurse to fill the next slot from the cells still unused.
  11. Place nums[0]=1 at depth 1: path becomes [2, 1], used[0] <- TRUE. Recurse to fill the next slot from the cells still unused.
  12. Place nums[1]=1 at depth 2: path becomes [2, 1, 1], used[1] <- TRUE. Its twin nums[0] is already in the path, so this duplicate is allowed. Recurse to fill the next slot from the cells still unused.
  13. All 3 cells are used, so the path [2, 1, 1] is a complete permutation. Record a copy: 3 found so far. Now unwind one level and give that slot its next candidate.
  14. Skip nums[1]=1: it equals nums[0]=1, and that twin is NOT in the path. Whatever this branch would build, the branch that started with nums[0] already built the same ordering, since the two 1s are indistinguishable. Placing a duplicate is only allowed after its left twin is placed, so each group of equals is consumed left to right exactly once.
  15. Every branch is explored and unwound. 3 unique permutations: [1, 1, 2], [1, 2, 1], [2, 1, 1]. Without the skip rule the 3! = 6 index orderings would have produced 3 duplicate lists that a set would then have to throw away; the sorted-twin check prunes them before they are built.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Permutations II in the editorAll Backtracking problemsBack to roadmap