Permutations II
Generate all unique permutations of numbers that may repeat: sort, then skip a value when its equal left neighbour is not yet in the path.
Problem Understanding
Permutations II: given numbers nums that may contain duplicates, return every unique permutation, in any order.
Example: nums = [1, 1, 2] returns [[1,1,2], [1,2,1], [2,1,1]]. Plain permutations would list each of these twice.
The Intuition: Use Equal Values in Order
Start from Permutations: choose an unused number, recurse, un-choose. With duplicates, two equal values can swap places and produce the same list twice.
The fix is a single rule after sorting:
- Skip
nums[i]ifnums[i] == nums[i − 1]andnums[i − 1]is not in the path.
That makes equal values always enter the path left to right, so there is only one way to place each group of twins. The same sort-and-skip idea removes duplicates in Subsets II and Combination Sum II.
Interactive Walkthrough
The sorted numbers are on top, with used ones tinted; a twin skipped by the rule turns red. The path is below, and the unique permutations collect beside the figure. Try Two pairs: 24 orderings collapse to 6.
Dry Run Table
Input: nums = [1, 1, 2] (indexes 0, 1, 2)
| Path | Index tried | Action |
|---|---|---|
| [] | 0 (1) | choose |
| [1] | 1 (1) | choose: twin 0 is used |
| [1, 1] | 2 (2) | choose, record [1,1,2] |
| [1] | 2 (2) | choose, then index 1: record [1,2,1] |
| [] | 1 (1) | skip: twin 0 is unused |
| [] | 2 (2) | choose, then 0, 1: record [2,1,1] |
Answer: 3 unique permutations.
The Solution Template
The Permutations template plus a sort and one skip check.
Permutations II Code
1var permuteUnique = function(nums) {2 nums.sort((a, b) => a - b);3 const res = [], path = [], used = new Array(nums.length).fill(false);4 const backtrack = () => {5 if (path.length === nums.length) {6 res.push([...path]);7 return;8 }9 for (let i = 0; i < nums.length; i++) {10 if (used[i]) continue;11 if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;12 used[i] = true;13 path.push(nums[i]);14 backtrack();15 path.pop();16 used[i] = false;17 }18 };19 backtrack();20 return res;21};
Edge Cases & Common Mistakes
- Forgetting to sort: the skip rule only works when equal values are adjacent.
used[i − 1]instead of!used[i − 1]: also produces unique results but explores far more dead branches; the!usedform prunes at the top.- All values equal: exactly one permutation.
- No duplicates: the rule never fires, and the result is the same as Permutations.
- Deduplicating with a set afterwards: correct but wasteful; skip during the search instead.
Summary
Sort the numbers, then run the choose / recurse / un-choose template with one extra rule: skip nums[i] when it equals nums[i − 1] and nums[i − 1] is unused. Equal values are then always placed in order, so every unique permutation is built exactly once.
More practice: DSA interview questions with answers · patterns cheat sheet