Generate Parentheses

Medium

Problem

Return every well-formed string made of n pairs of parentheses.

Example 1

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

Test cases

Case 1

Input:    3
Expected (any order): ["((()))","(()())","(())()","()(())","()()()"]

Case 2

Input:    1
Expected (any order): ["()"]

Case 3

Input:    2
Expected (any order): ["(())","()()"]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Backtracking with open/close counts

Time O(4^n / √n) — the nth Catalan numberSpace O(n)

Add "(" while fewer than n are open; add ")" only while it would not exceed the opens. Every leaf is valid — no filtering needed.

function generateParenthesis(n) {
const res = [];
const bt = (cur, open, close) => {
if (cur.length === 2 * n) { res.push(cur); return; }
if (open < n) bt(cur + '(', open + 1, close);
if (close < open) bt(cur + ')', open, close + 1);
};
bt('', 0, 0);
return res;
}