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.

• Backtracking
• Dynamic Programming

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

JavaScript

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;
 }

TypeScript

Written by @manishh12

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

   const backtrack = (cur: string, open: number, close: number): void => {
     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;
 }

Python

Written by @manishh12

 class Solution:
     def generateParenthesis(self, n: int) -> List[str]:
         result = []

         def backtrack(cur: str, open: int, close: int):
             if len(cur) == n * 2:
                 result.append(cur)
                 return

             if open < n:
                 backtrack(cur + '(', open + 1, close)
             if close < open:
                 backtrack(cur + ')', open, close + 1)

         backtrack('', 0, 0)
         return result

Java

Written by @manishh12

 class Solution {
     public List<String> generateParenthesis(int n) {
         List<String> result = new ArrayList<>();

         backtrack(result, "", 0, 0, n);
         return result;
     }

     private void backtrack(List<String> result, String cur, int open, int close, int n) {
         if (cur.length() == n * 2) {
             result.add(cur);
             return;
         }

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

C++

Written by @manishh12

 class Solution {
 public:
     vector<string> generateParenthesis(int n) {
         vector<string> result;
         backtrack(result, "", 0, 0, n);
         return result;
     }

 private:
     void backtrack(vector<string>& result, string cur, int open, int close, int n) {
         if (cur.length() == n * 2) {
             result.push_back(cur);
             return;
         }

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

Complexity Analysis

• Time Complexity: $O(4^n / \sqrt{n})$
• Space Complexity: $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, $C_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

• LeetCode Problem: LeetCode Problem
• Solution Link: Generate Parantheses Solution on LeetCode
• Authors LeetCode Profile: Manish Kumar Gupta

---