N-Queens
Places N queens on an N×N chessboard so no two queens threaten each other.
Generates all valid combinations of balanced parentheses.
Generate Parentheses is a classic backtracking problem: given n pairs of parentheses, generate all strings that contain properly balanced (well-formed) combinations of opening and closing parentheses. This problem is a favorite in coding interviews because it elegantly demonstrates constrained backtracking with a simple invariant, and its solution count follows the famous Catalan number sequence, connecting it to a rich web of combinatorial structures studied for over two centuries.
The Catalan numbers, which count the valid parenthesizations, are named after Belgian mathematician Eugene Charles Catalan, who described them in 1838. However, the sequence was known earlier: Euler enumerated the number of ways to triangulate a polygon in the 1750s (another Catalan-counted structure), and the Mongolian mathematician Mingantu discovered the sequence around 1730. The parenthesization problem itself connects to the work of early computer scientists on expression parsing. When developing compilers in the 1950s and 1960s, researchers needed to understand how expressions could be grouped with parentheses -- the same structural question that this algorithm answers by enumeration.
The invariant that closing count never exceeds opening count at any prefix of the string is both necessary and sufficient for validity. This makes the constraint check trivially simple -- just compare two integers -- yet it produces only well-formed strings with zero wasted exploration.
| Metric | Value |
|---|---|
| Valid combinations | C(n) (nth Catalan number) |
| Time | O(4^n / sqrt(n)) |
| Space | O(n) |
The number of valid combinations follows the Catalan number sequence: 1, 1, 2, 5, 14, 42, 132, 429, 1430, ... For n = 3, there are 5 valid combinations; for n = 5, there are 42; for n = 10, there are 16,796. The Catalan number formula is C(n) = (2n)! / ((n+1)! * n!), and its asymptotic growth is approximately 4^n / (n^(3/2) * sqrt(pi)).
The Catalan numbers appear in a astonishing variety of combinatorial contexts -- Richard Stanley has catalogued over 200 distinct structures counted by Catalan numbers. Among them: the number of distinct binary trees with n nodes, the number of ways to triangulate a convex polygon with n+2 sides, the number of monotonic lattice paths from (0,0) to (n,n) that stay below the diagonal, the number of ways to pair 2n points on a circle without crossing connections, and the number of distinct full parenthesizations of a product of n+1 factors. Generating valid parentheses is thus not just a programming exercise but a window into one of the most ubiquitous structures in discrete mathematics.
In formal language theory, the valid parenthesizations are called Dyck words, named after German mathematician Walther von Dyck. A Dyck word of order n is a string of n opening and n closing brackets where every prefix has at least as many opening brackets as closing ones. The set of all Dyck words forms a context-free language generated by the grammar S -> (S)S | empty. This connection to formal grammars means that parenthesis generation relates directly to parsing theory, compiler design, and the study of pushdown automata.
This problem is a popular interview question and a clean example of constrained backtracking where the constraints are simple enough to check inline with two integer comparisons. The same pattern applies to generating valid expressions, balanced brackets of multiple types (where a stack-based check replaces the simple counter), and recursive language structures. Understanding Generate Parentheses provides intuition about Catalan numbers, Dyck paths, and the power of maintaining simple invariants during recursive enumeration.