22. Generate Parentheses

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Only build valid prefixes: add '(' while fewer than n are open, and add ')' only when it would close an open one.

1function generateParenthesis(n: number): string[] {
2  const res: string[] = [], path: string[] = [];
3  function dfs(open: number, close: number) {
4    if (path.length === 2 * n) { res.push(path.join("")); return; }
5    if (open < n) { path.push("("); dfs(open + 1, close); path.pop(); }
6    if (close < open) { path.push(")"); dfs(open, close + 1); path.pop(); }
7  }
8  dfs(0, 0);
9  return res;
10}

open = 1close = 0

path

(

result

empty

open 0 < 3: add '('.

1 / 0

Space: play/pause · ←/→: step