Last updated on January 13th, 2025 at 03:10 am

Here, we see a Generate Parentheses LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Backtracking, String

Companies

Google, Uber, Zenefits

Level of Question

Medium

Generate Parentheses LeetCode Solution

1. Problem Statement

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

Example 1:
Input: n = 3
Output: [“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

Example 2:
Input: n = 1
Output: [“()”]

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Backtracking”. Backtracking is a general algorithmic technique for solving problems incrementally, by trying partial solutions and then abandoning them if they are not suitable. In this case, the problem involves generating all valid combinations of parentheses, which is a classic backtracking problem.

3. Code Implementation in Different Languages

3.1 Generate Parentheses C++

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        int open = n;
        int close = n;
        vector<string> ans;
        string op = "";
        solve(op, open, close, ans);
        return ans;        
    }
        void solve(string op, int open, int close, vector<string> &ans){
        if(open == 0 && close == 0){
            ans.push_back(op);
            return;
        } 
        if(open == close){
            string op1 = op;
            op1.push_back('(');
            solve(op1, open-1, close, ans);
        }
        else if(open == 0){
            string op1 = op;
            op1.push_back(')');
            solve(op1, open, close-1, ans);
        }
        else if(close == 0){
            string op1 = op;
            op1.push_back('(');
            solve(op1, open-1, close, ans);
        }
        else{
            string op1 = op;
            string op2 = op;
            op1.push_back('(');
            op2.push_back(')');
            solve(op1, open-1, close, ans);
            solve(op2, open, close-1, ans);
        }
    }
};

3.2 Generate Parentheses Java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        recurse(res, 0, 0, "", n);
        return res;
    }
    public void recurse(List<String> res, int left, int right, String s, int n) {
        if (s.length() == n * 2) {
            res.add(s);
            return;
        }
        if (left < n) {
            recurse(res, left + 1, right, s + "(", n);
        }
        if (right < left) {
            recurse(res, left, right + 1, s + ")", n);
        }
    }
}

3.3 Generate Parentheses JavaScript

var generateParenthesis = function(n) {
  const output = [];
  const dfs = (str, open, close) => {
    if (open > close) {
      return;
    }
    if (open === 0 && close === 0) {
      output.push(str);
      return;
    }
    if (open > 0) {
      dfs(`${str}(`, open - 1, close);
    }
    if (close > 0) {
      dfs(`${str})`, open, close - 1);
    }
  };
  dfs('', n, n);
  return output;
};

3.4 Generate Parentheses Python

class Solution(object):
    def generateParenthesis(self, n):
	    def dfs(left, right, s):
		    if len(s) == n * 2:
			    res.append(s)
			    return 
		    if left < n:
			    dfs(left + 1, right, s + '(')
		    if right < left:
			    dfs(left, right + 1, s + ')')
	    res = []
	    dfs(0, 0, '')
	    return res