Permutations II
The key idea
Sort the numbers first so equal values sit next to each other. Then, at each position, skip a value if it equals its left neighbor AND that left neighbor has not been used in the current path — that one rule prunes every duplicate permutation without ever building one.
Problem
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
A permutation is an arrangement of all the elements of nums. Because nums may contain repeated values, naively generating every arrangement would yield duplicate permutations; you must return each distinct arrangement exactly once.
Constraints
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
Examples
Input: nums = [1,1,2]
Output: [[1,1,2],[1,2,1],[2,1,1]]
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Complexity
Time: O(n * n!) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Backtracking problems
- Combination SumMEDIUM
- Combination Sum IIMEDIUM
- Combination Sum IIIMEDIUM
- CombinationsMEDIUM
- Generate ParenthesesMEDIUM
- Letter Combinations of a Phone NumberMEDIUM
- Matchsticks to SquareMEDIUM
- N-QueensHARD
- N-Queens IIHARD
- Non-decreasing SubsequencesMEDIUM
- Palindrome PartitioningMEDIUM
- Partition to K Equal Sum SubsetsMEDIUM