Skip to main content

Generate Parentheses Solution

In this page, we will solve the Generate Parentheses problem using different approaches: backtracking and dynamic programming. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

Problem Description​

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Examples​

Example 1:

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

Example 2:

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

Constraints​

  • 1 <= n <= 8

Follow up: Can you come up with an algorithm that uses backtracking to generate all combinations of well-formed parentheses?


Solution for Generate Parentheses Problem​

Intuition and Approach​

The problem can be solved using backtracking or dynamic programming. The backtracking approach is more intuitive and efficient for this problem.

Approach 1: Backtracking​

The backtracking approach involves generating all possible combinations of parentheses and then filtering out the valid ones. Instead of generating all combinations, we can generate only valid combinations by ensuring that at any point in the recursion, the number of closing parentheses does not exceed the number of opening parentheses.

Implementation​

Live Editor
function generateParentheses() {
  const n = 3;

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

    const backtrack = (cur, open, close) => {
      if (cur.length === n * 2) {
        result.push(cur);
        return;
      }

      if (open < n) {
        backtrack(cur + '(', open + 1, close);
      }
      if (close < open) {
        backtrack(cur + ')', open, close + 1);
      }
    };

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

  const result = generateParenthesis(n);
  return (
    <div>
      <p>
        <b>Input:</b> n = {n}
      </p>
      <p>
        <b>Output:</b> {JSON.stringify(result)}
      </p>
    </div>
  );
}
Result
Loading...

Codes in Different Languages​

Written by @manishh12
 function generateParenthesis(n) {
const result = [];

const backtrack = (cur, open, close) => {
if (cur.length === n * 2) {
result.push(cur);
return;
}

if (open < n) {
backtrack(cur + '(', open + 1, close);
}
if (close < open) {
backtrack(cur + ')', open, close + 1);
}
};

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

Complexity Analysis​

  • Time Complexity: O(4n/n)O(4^n / \sqrt{n})
  • Space Complexity: O(4n/n)O(4^n / \sqrt{n})
  • Where n is the number of pairs of parentheses.
  • The time complexity is based on the number of valid combinations which is the nth Catalan number, Cn=1n+1(2nn)≈4nnnC_n = \frac{1}{n+1}\binom{2n}{n} \approx \frac{4^n}{n\sqrt{n}}.
  • The space complexity is determined by the number of valid combinations as well.
Note

By using both backtracking and dynamic programming approaches, we can efficiently solve the Generate Parentheses problem. The backtracking approach is more straightforward and intuitive, while the dynamic programming approach leverages previously computed results to build the solution.

References​