Generate parentheses (backtracking)

Medium TimeO(4ⁿ / √n) (Catalan) SpaceO(n) stack

An arrangement of brackets is well formed when every opener is closed after it and no closer ever appears before the opener it would match. Given n pairs, return every well-formed arrangement. Each result holds exactly n opening and n closing brackets, at no point may the closers outnumber the openers, and each arrangement appears once.

Examples

Example 1

Input
n = 3
Output
["((()))","(()())","(())()","()(())","()()()"]
Five well-formed arrangements of 3 pairs, out of the 20 ways to order 3 of each.

Example 2

Input
n = 1
Output
["()"]
One pair can only be written one way: )( closes a bracket that was never opened.

The Code

function backtrack(current, open, close, n, result) {
  if (current.length === 2 * n) {
    result.push(current);
    return;
  }
  if (open < n) backtrack(current + '(', open + 1, close, n, result);
  if (close < open) backtrack(current + ')', open, close + 1, n, result);
}
function generateParenthesis(n) {
  const result = [];
  backtrack('', 0, 0, n, result);
  return result;
}
generateParenthesis(3);
Done

The first 15 calls, of 23. This one does not fit on a page.

Step through generateParenthesis(3) call by call

More like this

All backtracking examples (10) →