Pattern visualizer

Permutations II

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. Animated on: nums = [1, 1, 2], which contains a duplicate. Return every unique permutation. Answer: [1, 1, 2], [1, 2, 1], [2, 1, 1]..

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

time O(n * n!)space O(n) recursion and flags, beyond the outputstep 1 / 15

[0]

[1]

[2]

line 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.

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

Where to practice Backtracking

Practice Backtracking problems All Backtracking problems Back to roadmap