Generate balanced parentheses
Generate every well-formed string containing a requested number of matching parenthesis pairs.
Course progress
Problem 96 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
pairs = 3
Expected output
((())) (()()) (())() ()(()) ()()()
What is happening?
Backtracking never closes more pairs than it has opened. Exploring every legal choice produces the five well-formed strings for three pairs.
Solution strategy
Build the right mental model
Add an opening parenthesis while any remain, and add a closing one only when it cannot outnumber the openings already used.
Core concepts
backtracking · constraint tracking
Complexity
Time O(Cn x n) including output, call-stack space O(n), where Cn is the nth Catalan number.
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for generate-parentheses
using System;
using System.Collections.Generic;
class Program
{
static void Generate(int pairs, int open, int close, string current, List<string> results)
{
if (current.Length == pairs * 2) { results.Add(current); return; }
if (open < pairs) Generate(pairs, open + 1, close, current + "(", results);
if (close < open) Generate(pairs, open, close + 1, current + ")", results);
}
static void Main()
{
var results = new List<string>();
Generate(3, 0, 0, "", results);
Console.WriteLine(string.Join(" ", results));
}
}Knowledge check
Questions students often ask
What is the main idea behind generate balanced parentheses?
Add an opening parenthesis while any remain, and add a closing one only when it cannot outnumber the openings already used.
What is the time and space complexity of this solution?
Time O(Cn x n) including output, call-stack space O(n), where Cn is the nth Catalan number.
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.