Generate Parentheses Medium 0 attempts
LeetCode ↗

Generate Parentheses

Medium StringHash Table LeetCode

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

Every open parenthesis must have a matching close, and at no point should the number of closing parentheses exceed the number of opening ones.

Examples

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

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

Constraints

  • 1 <= n <= 8
Sample Input
n = 3
Sample Output
["((()))","(()())","(())()","()(())","()()()"]
Constraints
  • 1 <= n <= 8
Test Cases
Case 1
Args: [3] Expected: ["((()))","(()())","(())()","()(())","()()()"]
Topics
StringHash Table

Backtrack while keeping a count of open and close parentheses used. Add '(' if the open count is below n. Add ')' only if the close count is below the open count — this guarantees the string stays valid at every step.

function generateParenthesis(n) {
  const result = [];

  function backtrack(current, open, close) {
    if (current.length === 2 * n) {
      result.push(current);
      return;
    }
    if (open < n) {
      backtrack(current + '(', open + 1, close);
    }
    if (close < open) {
      backtrack(current + ')', open, close + 1);
    }
  }

  backtrack('', 0, 0);
  return result;
}

Time: O(4^n / √n) — the nth Catalan number bounds the valid combinations. Space: O(n) for the recursion stack.

Saved in this browser only. Private to you.

JavaScript