Practice › Recursion & Backtracking
Generate Parentheses
Medium · Recursion & Backtracking · Asked at Google, Amazon, Microsoft, Uber
Print all combinations of n pairs of well-formed parentheses in lexicographic order (where ( comes before )).
Input
One integer n.
Output
Each combination on its own line.
Constraints
- 1 ≤ n ≤ 8
Add
(while open < n, add)while close < open — trying(first gives lexicographic order.
Example 1
Input
3
Output
((())) (()()) (())() ()(()) ()()()
Example 2
Input
1
Output
()
Hints
- Build the string one character at a time, tracking how many ( and ) you have used.
- You may add ( while open < n, and ) while close < open. Trying ( first produces lexicographic order.
Approach
Backtracking with two counters. A prefix can still become valid only if close <= open <= n, so those are the only moves allowed. Trying ( before ) at every step generates the strings in lexicographic order, since ( < ). When the length reaches 2n, print the string. The number of results is the n-th Catalan number (1430 for n = 8).
Complexity: O(Catalan(n) · n) time · O(n) recursion depth
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int n;
string cur;
void go(int open, int close) {
if ((int)cur.size() == 2 * n) {
cout << cur << "\n";
return;
}
if (open < n) {
cur.push_back('(');
go(open + 1, close);
cur.pop_back();
}
if (close < open) {
cur.push_back(')');
go(open, close + 1);
cur.pop_back();
}
}
int main() {
cin >> n;
go(0, 0);
return 0;
}Python solution
n = int(input())
out = []
def go(cur, open_, close):
if len(cur) == 2 * n:
out.append(cur)
return
if open_ < n:
go(cur + "(", open_ + 1, close)
if close < open_:
go(cur + ")", open_, close + 1)
go("", 0, 0)
print("\n".join(out))Java solution
import java.util.*;
public class Main {
static int n;
static StringBuilder out = new StringBuilder();
static void go(StringBuilder cur, int open, int close) {
if (cur.length() == 2 * n) {
out.append(cur).append('\n');
return;
}
if (open < n) {
cur.append('(');
go(cur, open + 1, close);
cur.deleteCharAt(cur.length() - 1);
}
if (close < open) {
cur.append(')');
go(cur, open, close + 1);
cur.deleteCharAt(cur.length() - 1);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
go(new StringBuilder(), 0, 0);
System.out.print(out);
}
}