27. Generate Parentheses

MediumString Backtracking Recursion

Given an integer n, return every string made of exactly n opening brackets ( and n closing brackets ) that is well-formed.

A string is well-formed when every ) closes an earlier unmatched ( and nothing is left open at the end. Each string must appear once; the order of the list does not matter.

Example 1

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

Example 2

Input: n = 1
Output: ["()"]

Constraints

1 <= n <= 8

💡 Hint 1

Build the string one character at a time. When is it legal to add (, and when is it legal to add )?

💡 Hint 2

You may add ( while fewer than n have been used, and ) only while it would close something (closed < opened).

💡 Hint 3

If you only ever make legal moves, every string of length 2n you reach is valid, so no filtering is needed.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Backtracking over prefixes that can still be completed. Track how many brackets have been opened and closed so far. Adding ( is allowed while open < n; adding ) is allowed while close < open, so a closer always has something to match. Since every move keeps the prefix valid, each time the prefix reaches length 2n it is a complete well-formed string and goes straight into the result. The search never explores a dead end, so the work is proportional to the size of the output (the n-th Catalan number of strings, each of length 2n).

Time O(4^n / √n)Space O(n) besides the output

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

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

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

/**
 * @param {number} n
 * @return {string[]}
 */
function generateParenthesis(n) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit