Generate Parentheses

Given n, generate every string of n pairs of parentheses that is balanced (well-formed).

Example

Text

n = 3  ->  ["((()))", "(()())", "(())()", "()(())", "()()()"]
n = 1  ->  ["()"]

Backtracking builds a solution one choice at a time. After exploring everything that follows a choice, it undoes the choice (backtracks) and tries the next option. Every problem in this section follows that pattern.

Brute force: generate everything, keep the valid ones

Generate all 2^(2n) strings of length 2n made of ( and ), and keep the balanced ones. A string is balanced if a running count (+1 for (, -1 for )) never goes negative and ends at 0.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static boolean isBalanced(CharSequence s) {
        int depth = 0;
        for (int i = 0; i < s.length(); i++) {
            depth += s.charAt(i) == '(' ? 1 : -1;
            if (depth < 0) return false;
        }
        return depth == 0;
    }

    static void generateAll(StringBuilder current, int len, List<String> out) {
        if (current.length() == len) {
            if (isBalanced(current)) out.add(current.toString());
            return;
        }
        for (char c : new char[]{'(', ')'}) {
            current.append(c);
            generateAll(current, len, out);
            current.deleteCharAt(current.length() - 1);
        }
    }

    static List<String> generateParentheses(int n) {
        List<String> out = new ArrayList<>();
        generateAll(new StringBuilder(), 2 * n, out);
        return out;
    }

    public static void main(String[] args) {
        System.out.println(generateParentheses(3));
    }
}

Output

[((())), (()()), (())(), ()(()), ()()()]

StringBuilder is a mutable string buffer. append adds a character and deleteCharAt removes one, so the same buffer is reused and toString() copies it only for a finished answer.

Time: O(2^(2n) · n). For n = 3, 64 strings are built for 5 answers. Space: O(n) besides the output.

Optimal: only build valid prefixes

A prefix can always be extended to a balanced string as long as:

it has at most n opening parentheses, and
it never has more ) than (.

So add ( only while open < n, and add ) only while close < open. Every complete string built this way is balanced, and no work is wasted on dead ends.

graph TB
    a["("] --> b["(("]
    a --> c["()"]
    b --> d["(()"]
    b --> e["((("]
    c --> f["()("]

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static void backtrack(StringBuilder current, int open, int close, int n, List<String> out) {
        if (current.length() == 2 * n) {
            out.add(current.toString());
            return;
        }
        if (open < n) {
            current.append('(');
            backtrack(current, open + 1, close, n, out);
            current.deleteCharAt(current.length() - 1);
        }
        if (close < open) {
            current.append(')');
            backtrack(current, open, close + 1, n, out);
            current.deleteCharAt(current.length() - 1);
        }
    }

    static List<String> generateParentheses(int n) {
        List<String> out = new ArrayList<>();
        backtrack(new StringBuilder(2 * n), 0, 0, n, out);
        return out;
    }

    public static void main(String[] args) {
        System.out.println(generateParentheses(3));
        System.out.println(generateParentheses(1) + " " + generateParentheses(10).size());
        List<String> none = generateParentheses(0);
        System.out.println(none.size() + " " + none.get(0).isEmpty());
    }
}

Output

[((())), (()()), (())(), ()(()), ()()()]
[()] 16796
1 true

List.toString prints strings without quotes, so () in the output is the string "()".

Time: O(Cₙ · n), where Cₙ is the nth Catalan number (16796 for n = 10), the number of balanced strings. Each is copied in O(n). Space: O(n) for the recursion and the current string, besides the output.

Edge cases

n = 0: one answer, the empty string. The last line of the program prints the list size and whether that answer is empty.
Order: trying ( before ) produces the strings in lexicographic order, because '(' < ')'.