Generate Parentheses Leetcode Solution

In this post, we are going to solve the Generate Parentheses Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Table of Contents

Problem

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: ["()"]

Constraints:

1 <= n <= 8

Now, let’s see the leetcode solution of Generate Parentheses Leetcode Solution.

Generate Parentheses Leetcode Solution in Python

class Solution:
  def generateParenthesis(self, n):
    ans = []

    def dfs(l: int, r: int, s: str) -> None:
      if l == 0 and r == 0:
        ans.append(s)
      if l > 0:
        dfs(l - 1, r, s + '(')
      if l < r:
        dfs(l, r - 1, s + ')')

    dfs(n, n, '')
    return ans

Generate Parentheses Leetcode Solution in CPP

class Solution {
 public:
  vector<string> generateParenthesis(int n) {
    vector<string> ans;

    dfs(n, n, "", ans);
    return ans;
  }

 private:
  void dfs(int l, int r, string&& path, vector<string>& ans) {
    if (l == 0 && r == 0) {
      ans.push_back(path);
      return;
    }

    if (l > 0) {
      path.push_back('(');
      dfs(l - 1, r, move(path), ans);
      path.pop_back();
    }
    if (l < r) {
      path.push_back(')');
      dfs(l, r - 1, move(path), ans);
      path.pop_back();
    }
  }
};

Generate Parentheses Leetcode Solution in Java

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

    dfs(n, n, new StringBuilder(), ans);
    return ans;
  }

  private void dfs(int l, int r, final StringBuilder sb, List<String> ans) {
    if (l == 0 && r == 0) {
      ans.add(sb.toString());
      return;
    }

    if (l > 0) {
      sb.append("(");
      dfs(l - 1, r, sb, ans);
      sb.deleteCharAt(sb.length() - 1);
    }
    if (l < r) {
      sb.append(")");
      dfs(l, r - 1, sb, ans);
      sb.deleteCharAt(sb.length() - 1);
    }
  }
}

Note: This problem Generate Parentheses is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.

NEXT: Merge k Sorted Lists