Generate Parentheses

Given a positive integer n, return every string made of exactly n opening and n closing parentheses that is balanced: reading left to right, you never close more parentheses than you have opened, and by the end every opening one has been closed.

Return the strings in any order, with no duplicates.

"Generate all valid X" means backtracking: build the string one character at a time, and only take steps that can still lead to a valid answer.

Here, validity comes down to two counts, opened and closed, of the characters placed so far:

• You can add ( as long as opened < n.
• You can add ) only if closed < opened, meaning there is an unmatched ( to close.

If you follow those two rules, every string you finish is balanced, and you never waste time on a prefix that's already broken. That's the difference from generating all 2^(2n) strings and filtering: the rules prune dead branches before they grow.

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

    def backtrack(opened: int, closed: int) -> None:
        if len(path) == 2 * n:
            results.append("".join(path))
            return
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return results

function generateParenthesis(n) {
  const results = [];
  const path = [];

  const backtrack = (opened, closed) => {
    if (path.length === 2 * n) {
      results.push(path.join(''));
      return;
    }
    if (opened < n) {
      path.push('(');
      backtrack(opened + 1, closed);
      path.pop();
    }
    if (closed < opened) {
      path.push(')');
      backtrack(opened, closed + 1);
      path.pop();
    }
  };

  backtrack(0, 0);
  return results;
}

State the two rules before writing any code, and explain why they're enough: the first keeps the total count right, and the second guarantees no prefix ever closes more than it opened. That justification is what the interviewer is listening for.

For complexity, it's fine to say "proportional to the number of valid strings, which is the n-th Catalan number, about 4ⁿ / n^1.5, times n to build each one." Naming Catalan numbers shows you understand why the output grows the way it does.