DSA problem

Permutations II

MediumBacktrackingPattern: Backtrackingtop600AmazonMicrosoftLinkedInBloombergGoogle

Given a collection nums that may contain duplicates, return all possible unique permutations in any order. Unlike the classic permutations problem, the input is no longer guaranteed to have distinct values, so a naive enumeration would produce n! permutations with many duplicates — for example [1,1,2] would yield 6 permutations of which only 3 are unique.

The brute-force fix would generate every permutation, push them into a set, and return the deduplicated list. That works but wastes time and memory on permutations that the algorithm should never have built in the first place. We want to prune duplicates at the source, during recursion, not after the fact.

The trick is two-fold. First, sort the input so that identical numbers sit next to each other. Then, in the recursive loop, refuse to pick nums[i] if nums[i] == nums[i - 1] and used[i - 1] is false. This condition says: "I am about to use a value identical to the one just to my left, but that left-side occurrence has not yet been used at this depth — meaning a previous branch already explored using that copy here, and trying this one would generate an identical permutation."

Apart from the duplicate-skipping rule, the rest of the algorithm is identical to standard permutation backtracking: maintain a used[] array and a growing path, recurse over indices, and snapshot a copy of path whenever it reaches length n. The dedupe rule fires O(n) times per level, so worst-case time is still bounded by O(n * unique_permutations) and space is O(n) for recursion and bookkeeping.

Examples

Example 1

Input: nums = [1,1,2]

Output: [[1,1,2],[1,2,1],[2,1,1]]

Explanation: Among the 6 raw permutations of [1,1,2], duplicates collapse to 3 unique arrangements.

Example 2

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Explanation: No duplicates in the input, so we get all 3! = 6 permutations exactly like the classic problem.

Example 3

Input: nums = [2,2,1,1]

Output: [[1,1,2,2],[1,2,1,2],[1,2,2,1],[2,1,1,2],[2,1,2,1],[2,2,1,1]]

Explanation: Four-element input with two pairs of duplicates produces 4! / (2! * 2!) = 6 unique permutations.

Constraints

1 <= nums.length <= 8
-10 <= nums[i] <= 10
The input may contain duplicate values.
The output must contain each unique permutation exactly once.
The order of permutations in the output does not matter.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

backtrackingarraysortingrecursion

Browse all DSA problems