Generate Parentheses

The problem

You are given a number n. Return a list of every string that is made of n opening parentheses "(" and n closing parentheses ")" and is balanced. Balanced means that every ")" closes one earlier "(" that is not closed yet, and that no "(" is left open at the end. For n = 2, "(())" and "()()" are balanced, and "())(" is not. List each string once. The order of the list does not matter.

What to write

function solve(n: number): string[]

Input
n = 1

Output
["()"]

Input
n = 2

Output
["(())","()()"]

Constraints

1 ≤ n ≤ 8.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   n is at most 8, so a string has at most 16 characters and the largest answer holds 1,430 strings. You have to write every one of them out, so no method can take fewer steps than the answer is long. The goal is to spend no time on strings that are not balanced.

2. Hint 2: Ask a smaller question

   Suppose n is 2 and a string starts with "((". Which character has to come next, and why? Now suppose it starts with "()". Which character has to come next this time? What did you count to decide?

3. Hint 3: Name the pattern

   The signal is "return every string that follows the rules". Build a string one character at a time. At each place, try a character the rules still allow, finish everything that can follow from it, then come back and try the other character. Exploring choices this way, and never taking a forbidden one, is backtracking. Read the lesson on backtracking.

4. Hint 4: State the invariant

   Every partial string has at most n opening parentheses and never more closing than opening ones. A string like that can always be finished into a balanced one, so no call is wasted. A string that reaches 2 × n characters this way is balanced.

5. Hint 5: Sketch the pseudocode

   extend(text, opened, closed): if text has 2 × n characters, add it to the answer and return. If opened < n, call extend(text + "(", opened + 1, closed). If closed < opened, call extend(text + ")", opened, closed + 1). Start with extend("", 0, 0), then return the answer.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Build only valid prefixes: open at most n pairs and never close more pairs than have been opened.

The slow way

Write every string of 2 × n characters that uses only "(" and ")", then keep the balanced ones. It is correct, but when n is 8 that means writing 65,536 strings to keep 1,430. Almost all of the work goes into strings that are thrown away.

The insight

You can tell early that a string cannot work. A partial string can still become balanced only while it has at most n opening parentheses and no more closing than opening ones. So add one character at a time and never add one that breaks either rule. Then every string you finish is balanced, and you never write a bad one.

Step by step

1. Keep a list for the finished strings. Finished strings turn up at different moments, deep inside different calls. One list that every call can reach collects them in one place.
2. Extend one partial string, knowing how many of each kind it has. The two counts are all that matters about the string so far when you decide what may come next. Passing them along saves counting the characters again in every call.
3. A string of 2n characters is complete: record it and stop. Only allowed characters were added, so a string of full length has n of each kind and is balanced. Nothing more may be added, so this call ends here.
4. Add an opening parenthesis if fewer than n are used. An opening parenthesis can always be closed later, so the only limit is the supply: a finished string has exactly n of them.
5. Add a closing parenthesis if an opening one is still unmatched. A closing parenthesis must close an earlier opening one, so there must be fewer closing than opening ones so far. Both choices start from the same string: adding a character builds a new string and leaves this one unchanged.
6. Start from the empty string and return every string recorded. The empty string has used nothing, so both counts start at 0. When this first call returns, every allowed way of adding characters has been tried.

The same numbered steps are the comments in each solution.

function solve(n) {
  // 1. Keep a list for the finished strings
  const out = [];
  // 2. Extend one partial string, knowing how many of each kind it has
  function visit(s, open, close) {
    // 3. A string of 2n characters is complete: record it and stop
    if (s.length === 2 * n) {
      out.push(s);
      return;
    }
    // 4. Add an opening parenthesis if fewer than n are used
    if (open < n) visit(s + "(", open + 1, close);
    // 5. Add a closing parenthesis if an opening one is still unmatched
    if (close < open) visit(s + ")", open, close + 1);
  }
  // 6. Start from the empty string and return every string recorded
  visit("", 0, 0);
  return out;
}

function solve(n: number): string[] {
  // 1. Keep a list for the finished strings
  const out: string[] = [];
  // 2. Extend one partial string, knowing how many of each kind it has
  function visit(s: string, open: number, close: number): void {
    // 3. A string of 2n characters is complete: record it and stop
    if (s.length === 2 * n) {
      out.push(s);
      return;
    }
    // 4. Add an opening parenthesis if fewer than n are used
    if (open < n) visit(s + "(", open + 1, close);
    // 5. Add a closing parenthesis if an opening one is still unmatched
    if (close < open) visit(s + ")", open, close + 1);
  }
  // 6. Start from the empty string and return every string recorded
  visit("", 0, 0);
  return out;
}

def solve(n):
    # 1. Keep a list for the finished strings
    result = []

    # 2. Extend one partial string, knowing how many of each kind it has
    def backtrack(current, opened, closed):
        # 3. A string of 2n characters is complete: record it and stop
        if len(current) == 2 * n:
            result.append(current)
            return
        # 4. Add an opening parenthesis if fewer than n are used
        if opened < n:
            backtrack(current + "(", opened + 1, closed)
        # 5. Add a closing parenthesis if an opening one is still unmatched
        if closed < opened:
            backtrack(current + ")", opened, closed + 1)

    # 6. Start from the empty string and return every string recorded
    backtrack("", 0, 0)
    return result

Example 2, traced

Input
n = 2

Output
["(())","()()"]

Why it works

Every string the calls build keeps two rules: at most n opening parentheses, and never more closing than opening ones. A full-length string that kept both is balanced. Every balanced string is found, because each of its beginnings keeps both rules too, so each next character is a choice that some call makes. Two different paths differ at some character, so no string is recorded twice.

Time and space

Time O(Cₙ · n), extra space O(n + output). Cₙ is the nth Catalan number, the count of balanced strings with n pairs. Each takes 2n characters to write, and no call works on a string that cannot be finished: O(Cₙ · n) time. The calls nest at most 2n + 1 deep, and the answer holds Cₙ strings.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Allow a closing parenthesis only while fewer closing than opening ones are used. If the test is "fewer than n closing ones" instead, n = 2 returns 6 strings, and 4 of them, such as "())(", are not balanced.
• A finished string has 2 × n characters, because n counts pairs. Stop at n characters and n = 2 returns "((" and "()", which are only the first halves of strings.
• If you build the string in one shared list of characters, remove the character you added after each call returns. Without that, old characters stay in the list, and n = 2 returns only "(())".

Pattern

Backtracking. Builds on Valid Parentheses and Count Good Nodes In Binary Tree.

Keep going