Abstract / Summary

Given a number n, list all valid combinations of n pairs of parentheses.

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 79% (3+ million submissions).

Typical patterns to solve this problem:

• Backtracking
• Dynamic Programming
• String

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 presented implementation produces all well-formed combinations of n pairs of parentheses. It builds a canonical string containing n opening and n closing brackets, then enumerates every distinct permutation of that string. Each permutation is examined for syntactic correctness; those that satisfy the balance condition are collected and returned as the final result.

Building the canonical string

The algorithm starts by constructing a string that consists of n opening parentheses followed by n closing parentheses. This deterministic ordering serves as the seed for the permutation generator.

string s;
for (int i = 0; i < n; i++)
    s += "(";
for (int i = 0; i < n; i++)
    s += ")";

By placing all opening brackets first, the initial arrangement is the lexicographically smallest permutation, which guarantees that next_permutation will eventually visit every unique ordering.

Enumerating permutations

The core loop employs the standard library function next_permutation to walk through all distinct permutations of the seed string. The loop is structured as a do … while construct, ensuring that the initial arrangement is also evaluated.

do
{
    // permutation handling logic
}
while (next_permutation(s.begin(), s.end()));

Because the seed string contains duplicate characters, next_permutation automatically skips over equivalent arrangements, reducing the number of iterations required to explore the full search space.

Early pruning of invalid candidates

Before performing a full balance check, the code verifies that the first character of the current permutation is an opening parenthesis. Any permutation that begins with a closing bracket cannot possibly represent a valid sequence, so the loop terminates early in that case.

if (s[0] != '(')
    break;

This simple test eliminates a large class of impossible candidates without incurring the cost of a full scan.

Balance verification

For each candidate permutation that passes the initial check, the algorithm walks through the characters while maintaining a depth counter. The counter increments for '(' and decrements for ')'. If the counter ever drops below zero, the sequence has more closing than opening brackets at that point, which violates the well-formedness rule. The loop aborts early in such a scenario.

bool ok = true;
int depth = 0;
for (auto c : s)
{
    if (c == '(')
        depth++;
    else
        depth--;

    if (depth < 0)
    {
        ok = false;
        break;
    }
}

If the scan completes without the depth becoming negative, the permutation is guaranteed to be balanced because the total number of opening and closing brackets is equal (by construction). The valid string is then added to the result collection.

if (ok)
    result.push_back(s);

Result accumulation

All strings that survive the balance verification are stored in a vector<string> named result. After the permutation loop finishes, the vector is returned to the caller.

vector<string> result;
...
return result;

Edge-case handling

The algorithm inherently respects the requirement that every generated sequence must contain exactly n opening and n closing parentheses, because the seed string is built with that precise count. The early check for a leading '(' ensures that sequences starting with a closing bracket are never considered, which aligns with the definition of a well-formed parenthetical expression. Additionally, the depth-tracking loop guarantees that any prefix of a candidate never has more closing than opening brackets, thereby enforcing the classic “no premature closing” rule.

Performance considerations

The use of next_permutation on a string with duplicated characters provides an implicit combinatorial pruning: only unique permutations are generated, avoiding redundant work that a naïve factorial-based enumeration would incur. The early exit when the first character is not '(' stops the entire enumeration as soon as the lexicographic order reaches a point where no further valid strings can appear, because all subsequent permutations would also start with ')'. Within the balance verification, the moment the depth counter becomes negative triggers an immediate break, preventing unnecessary traversal of the remainder of the string. These short-circuit mechanisms collectively reduce the number of character inspections performed across the whole search space.

The construction of the initial string using two simple loops runs in linear time relative to n, and the result vector grows only with valid combinations, ensuring that memory allocation is proportional to the output size rather than the total number of permutations examined.

Imagine you have a big pile of curly drawing tools called parentheses. Some look like little open mouths ready to eat, and some look like closed mouths that are finished. The goal is to put these together in a perfect line where every open mouth has a matching closed mouth to keep it company.

The code starts by taking all those open and closed shapes and mixing them up in every possible order. It is just like shaking up a bag of colored blocks to see all the different ways they can line up.

After it makes a new line, it checks to see if the row is happy. A row is happy if an open mouth always comes before a closed one. If it sees a closed mouth at the very front of the line, it knows that order will not work. It also walks along the line and keeps a tally by counting how many open mouths it sees. If the number of closed mouths ever gets bigger than the number of open ones, it knows the line is broken because a closed mouth cannot be by itself at the start.

Whenever it finds a line that stays perfectly balanced from the front all the way to the back, it saves that line in a special box so it can remember the right patterns for later. It keeps changing the order of the shapes over and over again until it has tried every possible way the shapes could sit in a row and has collected all the ones that work.

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

not analyzed yet

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	C++	Python	Java									TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#	Rust	JS			Go		PHP	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	begeekmyfriend							C
	BigEggStudy				C#
	black-shadows	C++
	bujosa					Rust
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	everthis						JS
	fartem								Ruby
	FelixFan1122				C#
	fengvyi	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost									Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lennylxx	C++
	linouk23	C++
	lkwq007		Python
	luangong	C++
	lzl124631x	C++
	MacJim	C++
	qiyuangong			Java
	ruoru					Rust
	Shamik07										Dart
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02							C
	vthwang			Java
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C++
linouk23	C++
lkwq007	Python
luangong	C++
lzl124631x	C++
MacJim	C++
qiyuangong	Java
ruoru	Rust
Shamik07	Dart
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
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