Pattern this teaches:Backtracking Basics
Permutations II
A medium Backtracking interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Backtracking
- Sheets
- 2
- Core for
- 0 roles
The problem
Given a collection of numbers that may contain duplicates, return all unique permutations. Two permutations are considered the same if they have the same elements in the same order.
Example 1
- Input
- nums = [7,4,4]
- Output
- [[4,4,7],[4,7,4],[7,4,4]]
- Why
- The two 4s are interchangeable, so only three orderings are distinct.
Example 2
- Input
- nums = [5,1,4]
- Output
- [[1,4,5],[1,5,4],[4,1,5],[4,5,1],[5,1,4],[5,4,1]]
- Why
- Three distinct values give all six permutations.
Constraints
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
How to think about it
Updated 2026-09-29When duplicate elements exist, any two identical numbers swap places invisibly to generate duplicate full permutations. The fix is to sort them and enforce a relative usage order: never pick an identical number if its identical predecessor has not already been picked in the active prefix.
Approaches, worst first
Generate all and filter with set
time O(n * n!) · space O(n * n!)
Run standard permutation generation, stringifying or collecting outputs into a set. If an input has many identical elements (such as eight 1s), this explores 8! = 40,320 branches just to produce a single unique answer.
Sort with boolean flag precedence
time O(n * n!) · space O(n)
Sort nums. Track used[i] booleans. At each position, loop i from 0 to n - 1. If used[i], continue. If i > 0, nums[i] == nums[i - 1], and !used[i - 1], skip nums[i]. This guarantees duplicate numbers are consumed strictly in left-to-right sequence.
Frequency map backtrackingWrite this one
time O(n * n!) · space O(n)
Count occurrences of each unique number into a hash map. Recurse over keys of the map; decrement count when placing a key and increment when backtracking. Naturally guarantees a number is placed at a given position at most once per distinct value.
Where people lose marks · 3
- Writing used[i - 1] instead of !used[i - 1] when skipping duplicate siblings. Skipping when used[i - 1] is true kills valid consecutive picks of identical numbers like [1, 1, 2].
- Using in-place element swapping with duplicate values without a local set at each recursion frame. In-place swapping scrambles sorted order, breaking adjacent duplicate checks.
- Neglecting to sort nums before starting the used-array backtracking algorithm.
The theory behind it
Backtracking — the ground this problem stands on. All Backtracking problems
What Backtracking is
Backtracking is an organized trial-and-error search through a maze of possibilities. You make a tentative choice, move forward to explore where that path leads, and if you hit a dead end or finish finding an answer, you back up and undo that choice. By cleaning up your changes before trying the next option, a single shared board or list is explored thoroughly without needing to clone full copies of your data at every turn.
When to reach for it
Reach for backtracking when a problem asks to generate all possible solutions, like all subsets, permutations, valid parentheses combinations, or word search paths on a board. Signals include puzzles with strict constraint rules, like placing eight non-attacking queens on a chessboard or solving a Sudoku grid. Whenever you must construct combinations step by step and abandon dead-end branches early before wasting time exploring impossible paths, use backtracking.
How the pattern works
Follow a three-step rhythm inside a loop: choose, explore, and unchoose. First, check if the current state satisfies your goal; if so, save a copy of it and return. Next, prune illegal moves immediately using constraint checks so unpromising branches are skipped. For each valid candidate, apply the move to your shared path or board, call the recursive function to explore deeper, and finally undo the move right after the call returns. Undoing restores the shared state so sibling choices start from a clean slate.
More Backtracking problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .