Log inSign up
mediumLeetCodeNot Started

Permutations II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

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 numbers into a sequence.

Example 1:

Input: nums = [1,1,2]
Output: [[1,1,2],[1,2,1],[2,1,1]]
Explanation: Since there are two 1's, standard permutation would yield 6 items with duplicates. Only 3 distinct unique permutations exist.

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: All 3! = 6 unique permutations are returned since all elements are distinct.

Constraints:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the distinction between sibling duplicates (!used[i-1]) and parent-child recursion path elements (used[i-1]).
  • Master duplicate pruning across combinatorial backtracking problems (Subsets II, Permutations II, Combination Sum II).
  • Formulate exact duplicate permutation counts using multinomial coefficient formulas.

1. Standard Permutations with Hash Set Deduplication

Intuition

Use a boolean array used of size N to track which indices are currently in the path. When the path reaches length N, serialize or insert the path list into a Hash Set. Finally, convert the set back to a 2D list.

Algorithm

  1. Step 1: Generate all N! permutations including duplicates using standard permutation backtracking.
  2. Step 2: Store generated permutations in a Hash Set to filter out identical sequences.
  3. Step 3: Convert the unique set entries into the final result list.
  4. Step 4: Return result list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <set>
4
5class Solution {
6public:
7 void backtrack(std::vector<int>& nums, std::vector<bool>& used, std::vector<int>& path, std::set<std::vector<int>>& uniquePerms) {
8 if (path.size() == nums.size()) {
9 uniquePerms.insert(path);
10 return;
11 }
12 for (int i = 0; i < (int)nums.size(); i++) {
13 if (used[i]) continue;
14 used[i] = true;
15 path.push_back(nums[i]);
16 backtrack(nums, used, path, uniquePerms);
17 path.pop_back();
18 used[i] = false;
19 }
20 }
21
22 std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) {
23 std::set<std::vector<int>> uniquePerms;
24 std::vector<bool> used(nums.size(), false);
25 std::vector<int> path;
26 backtrack(nums, used, path, uniquePerms);
27 return std::vector<std::vector<int>>(uniquePerms.begin(), uniquePerms.end());
28 }
29};
30
31int main() {
32 Solution solver;
33 std::vector<int> nums = {1, 1, 2};
34 std::vector<std::vector<int>> res = solver.permuteUnique(nums);
35 std::cout << "Brute Force Output:\n";
36 for (const auto& p : res) {
37 std::cout << "[ ";
38 for (int x : p) std::cout << x << " ";
39 std::cout << "]\n";
40 }
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N! * N) — Generates all N! permutations and copies each vector of length N into the set.
  • Space complexity: O(N! * N) — The Hash Set stores up to N! permutations of size N.

2. Frequency Map Backtracking

Intuition

By iterating only over distinct keys rather than array indices, we naturally prevent identical choices at any level. We decrement the frequency on descent and increment on backtrack.

Algorithm

  1. Step 1: At each recursion depth, use a local HashSet to record numbers already placed at the current position.
  2. Step 2: Swap elements in-place: for i = start to n - 1, if nums[i] was already used at this depth, skip.
  3. Step 3: Swap nums[start] and nums[i], recurse with start + 1, then backtrack swap.
  4. Step 4: Append completed permutations when start == n.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5class Solution {
6public:
7 void backtrack(std::unordered_map<int, int>& countMap, std::vector<int>& path, int n, std::vector<std::vector<int>>& result) {
8 if ((int)path.size() == n) {
9 result.push_back(path);
10 return;
11 }
12 for (auto& [num, count] : countMap) {
13 if (count > 0) {
14 path.push_back(num);
15 countMap[num]--;
16 backtrack(countMap, path, n, result);
17 countMap[num]++;
18 path.pop_back();
19 }
20 }
21 }
22
23 std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) {
24 std::unordered_map<int, int> countMap;
25 for (int num : nums) countMap[num]++;
26 std::vector<std::vector<int>> result;
27 std::vector<int> path;
28 backtrack(countMap, path, nums.size(), result);
29 return result;
30 }
31};
32
33int main() {
34 Solution solver;
35 std::vector<int> nums = {1, 1, 2};
36 std::vector<std::vector<int>> res = solver.permuteUnique(nums);
37 std::cout << "Frequency Map Output:\n";
38 for (const auto& p : res) {
39 std::cout << "[ ";
40 for (int x : p) std::cout << x << " ";
41 std::cout << "]\n";
42 }
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N * (N! / (k1! * k2!...))) — Explores exactly the unique permutation count multiplied by O(N) path copy cost.
  • Space complexity: O(N) — O(N) recursion stack and frequency map memory.

3. Sort + Used Array Duplicate Pruning

Intuition

Sorting groups duplicate numbers adjacent. If nums[i] == nums[i-1], we must only allow choosing nums[i] if nums[i-1] has already been picked in the current recursion path (used[i-1] == true). If !used[i-1], it means nums[i-1] was just processed and backtracked (sibling node at identical level), so picking nums[i] would duplicate that subtree.

When to apply: Industry standard gold optimal solution for permutations with duplicates.

Algorithm

  1. Step 1: Sort the input array nums in non-decreasing order upfront.
  2. Step 2: Maintain a boolean array used of length N to track elements in current branch.
  3. Step 3: Iterate i from 0 to N - 1. If used[i] is true, continue.
  4. Step 4: Key deduplication: If i > 0 && nums[i] == nums[i-1] && !used[i-1], continue (skip duplicate branch).
  5. Step 5: Mark used[i] = true, push nums[i] to current, recurse on solve(current), then backtrack.
  6. Step 6: When current.length == n, push a copy of current to result.

Duplicate-Pruned Permutation Tree Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Sort array to [1, 1, 2]
Visual state
Values and pointers at this exact step
tree
Root
path: []

Node order shown; add connections to display explicit tree edges.

Variables at this step
current
[]
used
[false,false,false]
Check / comparison
used = [F, F, F], available indices: 0, 1, 2
Decision / next transition
Pick index 0 (value 1)
Why this step matters

Sort array to [1, 1, 2]. Start at root with used = [F, F, F], current = [].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 void backtrack(std::vector<int>& nums, std::vector<bool>& used, std::vector<int>& path, std::vector<std::vector<int>>& result) {
8 if (path.size() == nums.size()) {
9 result.push_back(path);
10 return;
11 }
12 for (int i = 0; i < (int)nums.size(); i++) {
13 if (used[i]) continue;
14 // Prune duplicate sibling branch
15 if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
16
17 used[i] = true;
18 path.push_back(nums[i]);
19 backtrack(nums, used, path, result);
20 path.pop_back();
21 used[i] = false;
22 }
23 }
24
25 std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) {
26 std::sort(nums.begin(), nums.end());
27 std::vector<std::vector<int>> result;
28 std::vector<bool> used(nums.size(), false);
29 std::vector<int> path;
30 backtrack(nums, used, path, result);
31 return result;
32 }
33};
34
35int main() {
36 Solution solver;
37 std::vector<int> nums = {1, 1, 2};
38 std::vector<std::vector<int>> res = solver.permuteUnique(nums);
39 std::cout << "Optimal Output for [1, 1, 2]:\n";
40 for (const auto& p : res) {
41 std::cout << "[ ";
42 for (int x : p) std::cout << x << " ";
43 std::cout << "]\n";
44 }
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(N * (N! / (k1! * k2!...))) — Directly generates only the valid unique permutations without visiting dead redundant branches.
  • Space complexity: O(N) — O(N) for recursion call stack and boolean used array of size N.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Standard Permute + Hash Set)O(N! * N)O(N! * N)Generates massive redundant subtrees when duplicate counts are high.
2.Frequency Counter BacktrackingO(N * (N! / (k1!...)))O(N)Hash map lookup overhead per recursive state.
3.Sort + Used Array Pruning (Optimal)OptimalO(N * (N! / (k1!...)))O(N)Requires initial O(N log N) sort.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Writing if (i > 0 && nums[i] == nums[i-1] && used[i-1]) continue; instead of !used[i-1]. Using !used[i-1] ensures duplicate sibling branches are pruned while still allowing duplicate elements in deep parent-child paths.

Pitfall 2:

Forgetting to sort the array before invoking backtracking. Adjacent comparison nums[i] == nums[i-1] only works if identical elements are positioned together via sort().

Crucial Edge Cases to Validate:

  • Array with all identical elements (e.g., [1, 1, 1, 1]) -> exactly 1 unique permutation.
  • Array with all unique elements (e.g., [1, 2, 3]) -> exactly N! permutations.
  • Single element array (e.g., [1]) -> returns [[1]].
  • Array with multiple duplicate clusters (e.g., [1, 1, 2, 2]) -> correctly prunes both clusters.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the time complexity using multinomial formula N! / (k1! * k2! * ... * km!) to demonstrate mathematical rigor.
  2. Contrast used[i-1] vs !used[i-1] explicitly before coding to show deep clarity on backtracking call frames.
  3. Mention how the boolean array can be implemented using bit manipulation when N <= 32.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does !used[i-1] prune duplicates at the sibling level rather than the descendant level?

Back to DSA Sheet