What is the brute force approach and complexity for Permutations II?

Generate every index order, insert each ordering into a set, and let the set drop repeats with time complexity O(N! · N log N!) and space complexity O(N · N!).

What is the optimal approach and complexity for Permutations II?

Sort; at each slot skip a value if its equal left neighbour is unused with optimal time complexity O(N · N!) and space complexity O(N).

How do you identify the pattern for Permutations II?

Look for key signals in the prompt: "all unique permutations" indicates Order matters, so this is permutations. Unique means two copies of the same value must not give the same ordering twice.; "might contain duplicates" indicates Equal values create repeat answers, so we need a rule for the copies.; "in any order" indicates We only need the set of answers, so the search may skip repeats without changing the result..

Permutations II

Medium·LeetCode #47 Pro OnlySlight Variation

LeetCode

Problem Statement

You get a list nums that can contain repeated numbers. Return every distinct ordering of those numbers. Two orderings that look the same are listed only once.

The orderings can come back in any sequence.

Input

A list nums of integers. It may have repeated values and has between 1 and 8 numbers.

Output

A list of all distinct orderings. Each ordering holds every number once, and no ordering appears twice.

Example 1

Input: nums = [1, 1, 2]

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

The two 1s look alike. Swapping them gives the same ordering, so the 3! = 6 orderings collapse into 3 distinct ones.

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]]

No value repeats, so all 3! = 6 orderings are different.

Constraints

• 1 ≤ nums.length ≤ 8
• −10 ≤ nums[i] ≤ 10

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“all unique permutations”

→ Order matters, so this is permutations. Unique means two copies of the same value must not give the same ordering twice.

“might contain duplicates”

→ Equal values create repeat answers, so we need a rule for the copies.

“in any order”

→ We only need the set of answers, so the search may skip repeats without changing the result.

Approach Complexity Ladder

Brute Force — every order into a setO(N! · N log N!)O(N · N!)

Generate every index order, insert each ordering into a set, and let the set drop repeats

Optimal — sort, used[], and skip repeated copiesO(N · N!)O(N)

Sort; at each slot skip a value if its equal left neighbour is unused

Brute Force Intuition

Run the plain permutation search over the indices, with no special rule. Put each finished ordering into a set<vector<int>>. The set removes the repeats, but only after every duplicate has already been built.

Recognition rule for this sub-pattern:

Pick an unused element for each position; mark used, recurse, unmark.

Remember this · Backtracking

Trigger

"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.

Think

At each step, what are my choices, and how do I undo a choice?

Key question

What is my state, when is it complete, and when do I prune?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture