Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Add ( while open < n, add ) while close < open — trying ( first gives lexicographic order.

Example 1

Input

3

Output

((()))
(()())
(())()
()(())
()()()

Example 2

Input

1

Output

()

Hints

  1. Build the string one character at a time, tracking how many ( and ) you have used.
  2. 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);
    }
}

Solve Generate Parentheses online · All practice problems