Generate Parentheses

NeetCode: Generate Parentheses · LeetCode: 22. Generate Parentheses · Difficulty: Medium

Given n pairs of parentheses, return every well-formed combination.

Example

Text

Input:  n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Brute force: generate all strings, keep the valid ones

There are 2^(2n) strings of ( and ). Build them all and filter with the balance check. The recursion appends one character to a shared StringBuilder, recurses, then removes the character with setLength. out.add(current.toString()) copies the builder, so later changes do not alter stored results. A List<String> prints as [((())), ...] without quotes.

Java

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

class Solution {
    private boolean isValid(CharSequence s) {
        int balance = 0;
        for (int i = 0; i < s.length(); i++) {
            balance += s.charAt(i) == '(' ? 1 : -1;
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }

    private void build(StringBuilder current, int len, List<String> out) {
        if (current.length() == len) {
            if (isValid(current)) {
                out.add(current.toString());
            }
            return;
        }
        for (char c : new char[]{'(', ')'}) {
            current.append(c);
            build(current, len, out);
            current.setLength(current.length() - 1); // undo the append
        }
    }

    public List<String> generateParenthesis(int n) {
        List<String> out = new ArrayList<>();
        build(new StringBuilder(), 2 * n, out);
        return out;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.generateParenthesis(3));
        System.out.println(sol.generateParenthesis(1));
    }
}

Output

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

Time: O(2^(2n) · n). Space: O(n) for the recursion plus the output.

Optimal: backtracking that never builds an invalid prefix

Track how many ( and ) have been used. Add ( while fewer than n are used, and add ) only while fewer ) than ( have been used, so the prefix never goes negative. Every string reached at length 2n is valid, so no filter is needed and dead ends are never explored.

Java

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

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

    public List<String> generateParenthesis(int n) {
        List<String> out = new ArrayList<>();
        backtrack(0, 0, n, new StringBuilder(), out);
        return out;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.generateParenthesis(3));
        System.out.println(sol.generateParenthesis(1));
    }
}

Output

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

Time: O(4^n / √n), the n-th Catalan number of results, each built in O(n). Space: O(n) recursion depth beyond the output.