Generate Parentheses Medium 0 attempts
LeetCode ↗

Generate Parentheses

Medium StringHash Table LeetCode

Given a number n representing pairs of parentheses, produce every combination of parentheses that is properly balanced.

A combination is valid when every opening bracket has a matching closing bracket later on, and the closing brackets never outnumber the opening ones at any point while reading left to right.

Input Format
Implement generateParenthesis(n). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
n = 1
Output
["()"]
Constraints
  • 1 <= n <= 8
Test Cases (2)
Case 1
Args: [3] Expected: ["((()))","(()())","(())()","()(())","()()()"]
Case 2
Args: [1] 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.

javascript
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(n × Cn) = O(4^n / √n), where Cn is the nth Catalan number and each output string has length 2n. Space: O(n) for the recursion stack.

Saved in this browser only. Private to you.

JavaScript