Generate Parentheses

Approach Summary

Backtracking: add "(" if open < n; add ")" if close < open. Collect when len = 2n.

Full Solution & Approach

Every valid sequence of n pairs must be a balanced parenthesis string: at every prefix the number of closing brackets never exceeds the number of opening brackets, and the total counts are exactly n each. Generate candidates recursively with a backtracking function that tracks how many opening and closing brackets are already placed. At each step you may place an opening bracket as long as open < n, and you may place a closing bracket as long as close < open — this second condition is what guarantees every prefix stays balanced. When the path reaches length 2n, record it as a complete sequence. The search tree is exactly the set of valid sequences with no wasted branches, so the total work is proportional to the number of valid sequences, which is the n-th Catalan number, roughly 4^n / (n^(3/2) √π). Backtracking by removing the last character after each recursive call keeps the path reusable without copying. This is the standard template for generating constrained combinatorial strings — the same skeleton solves phone-number letter combinations and restore-IP-addresses.

The algorithm explores exactly the valid sequences, whose count is the n-th Catalan number C(n) = (1/(n+1))·C(2n, n) — O(C(n)) time. Each valid sequence is built and stored once; the recursion depth is at most 2n, giving O(n) space for the path plus the output.

Solution Code

Solution

def generate_parenthesis(n: int) -> list[str]:
    res = []

    def backtrack(open_count: int, close_count: int, path: list[str]) -> None:
        if len(path) == 2 * n:
            res.append(''.join(path))
            return
        if open_count < n:
            path.append('(')
            backtrack(open_count + 1, close_count, path)
            path.pop()
        if close_count < open_count:
            path.append(')')
            backtrack(open_count, close_count + 1, path)
            path.pop()

    backtrack(0, 0, [])
    return res

function generateParenthesis(n) {
  const res = [];
  function backtrack(open, close, path) {
    if (path.length === 2 * n) {
      res.push(path.join(''));
      return;
    }
    if (open < n) {
      path.push('(');
      backtrack(open + 1, close, path);
      path.pop();
    }
    if (close < open) {
      path.push(')');
      backtrack(open, close + 1, path);
      path.pop();
    }
  }
  backtrack(0, 0, []);
  return res;
}

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

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

vector<string> generateParenthesis(int n) {
    vector<string> res;
    string path;
    backtrack(n, 0, 0, path, res);
    return res;
}

void backtrack(int n, int open, int close, string& path, vector<string>& res) {
    if ((int)path.size() == 2 * n) {
        res.push_back(path);
        return;
    }
    if (open < n) {
        path.push_back('(');
        backtrack(n, open + 1, close, path, res);
        path.pop_back();
    }
    if (close < open) {
        path.push_back(')');
        backtrack(n, open, close + 1, path, res);
        path.pop_back();
    }
}

Edge Cases to Watch

n = 0 — the problem returns [""] (one empty string)
n = 1 — exactly ["()"]
Unbalanced prefixes are never generated because close < open gates the closing branch
n = 3 — the five classic sequences: ((())), (()()), (())(), ()(()), ()()()

How to Recognize This Pattern

"All valid combinations of n pairs of parentheses"
Constraint: close ≤ open ≤ n at all times

Complexity Analysis

Time Complexity

O(4ⁿ / √n)

Space Complexity

O(n)