Abstract / Summary

Given a list of numbers that may have duplicates generate all possible unique orderings of the list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 82% (3+ million submissions).

Typical patterns to solve this problem:

• Array
• Backtracking

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation generates all possible permutations of a given integer array. It leverages the C++ Standard Library to sort the input and then iteratively produce each lexicographically ordered arrangement using next_permutation. The result is collected in a two-dimensional vector that is returned to the caller.

Key Steps

The algorithm can be broken down into three distinct operations, each reflected in the source code.

Sorting the Input

Before permutation generation begins, the input vector is sorted to establish the smallest lexicographic order. This guarantees that next_permutation will enumerate every arrangement exactly once.

sort(nums.begin(), nums.end());

Iterative Generation with next_permutation

A do … while loop is employed so that the initial (sorted) configuration is captured before any transformation. Inside the loop, the current ordering of nums is appended to the result container. The loop continues as long as next_permutation can produce a new ordering.

do
{
    result.push_back(nums);
} while (next_permutation(nums.begin(), nums.end()));

Returning the Accumulated Permutations

After the loop terminates, the fully populated result vector, containing every permutation, is returned to the caller.

return result;

Edge Cases Handled

The logic naturally accommodates several boundary conditions without additional checks.

When the input vector is empty, the sort call is a no-op, and the do … while loop executes exactly once. Consequently, the function returns a vector containing a single empty permutation, which aligns with the mathematical definition of the permutation of an empty set.

For a single-element vector, sorting leaves the element unchanged, the loop records that sole arrangement, and next_permutation immediately reports that no further ordering exists. The result therefore consists of one permutation containing the original element.

If the input contains duplicate values, sorting groups identical elements together. next_permutation then traverses the space of distinct lexicographic sequences, effectively producing each unique permutation without repetition. This behavior ensures that the output does not contain duplicate rows even when the source data has repeated numbers.

Performance Optimizations

The implementation benefits from several implicit optimizations provided by the Standard Library.

Sorting the array once at the start establishes a deterministic starting point, allowing next_permutation to run in linear time per iteration without needing to recompute ordering from scratch.

Using next_permutation avoids recursive backtracking, which would otherwise require additional call-stack overhead and potentially repeated allocation of temporary containers. The iterative approach keeps the algorithm’s memory footprint low and makes use of in-place swaps, reducing the amount of data movement.

Appending each permutation with push_back stores the vectors contiguously in the result container, taking advantage of std::vector’s amortized allocation strategy. This results in efficient memory usage as the container grows to accommodate the full set of permutations.

Overall, the combination of a single sort, an in-place permutation generator, and contiguous storage yields a solution that is both concise and performant for the task of enumerating all permutations.

Imagine you have a handful of colorful building blocks laid out in a row. Sometimes you want to see every possible way to arrange those blocks in different orders. This computer code acts like a magical helper that finds all those different patterns for you.

First, the code lines up the blocks from the smallest to the largest one, just like tidying up before starting a game. Once they are in a nice, neat line, the computer takes a snapshot of that arrangement and puts it into a collection bag. Then, it uses a special trick to shuffle the blocks into the very next possible order. It keeps taking a new snapshot and shuffling the blocks over and over again. The computer is so clever that it knows exactly when it has tried every single possible combination, and once it has reached the very last one, it stops its work. Every time a new order is made, it gets tucked safely into the bag so you can see all the different ways the blocks can stand in a line.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: factorial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python	C++	Java								TS
	WalkCCC	Python	C++	Java
	leetcode.ca	Python	C++	Java	C#		Rust	JS	Go			TS
	LeetcodeHelp	Python	C++	Java
	MemoryLimitExceeded	Python	C++
	Progiez	Python	C++	Java
github	aylei						Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	Python
	bujosa	Python
	chandansgowda	Python
	charles-wangkai			Java
	chenyanzhe		C++
	Dijkstra-Edu			Java
	DimitrisJim					C
	everthis							JS
	fartem									Ruby
	FelixFan1122				C#
	fengvyi		C++
	fpdjsns	Python
	gaosq0604	Python
	Garvit244	Python
	gouthampradhan			Java
	halfrost								Go
	haoel		C++
	JoshCrozier							JS
	keineahnung2345		C++
	lennylxx					C
	linouk23		C++
	lkwq007	Python
	luangong		C++
	MacJim		C++
	muhammadfarhankt								Go
	qiyuangong	Python
	ruoru						Rust
	shreymehul				C#
	sonugiri1043		C++
	suxrobGM				C#
	trung-hn	Python
	varunu28			Java
	vli02					C
	vthwang			Java
	wisdompeak		C++
	XiaotaoGuo		C++
	yuanliu666										Kotlin
	YuriSpiridonov	Python
	zfang399		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	Python, Python
bujosa	Python
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	Python
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
muhammadfarhankt	Go
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality