22. Generate Parentheses LeetCode Solution

In this guide we will provide 22. Generate Parentheses LeetCode Solution with best time and space complexity. The solution to Generate Parentheses problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Problem Statement

Complexity Analysis

Generate Parentheses solution in C++
Generate Parentheses soution in Java
Generate Parentheses solution Python
Additional Resources

22. Generate Parentheses LeetCode Solution image

Problem Statement of Generate Parentheses

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

Complexity Analysis

Time Complexity: O(2^{2n})
Space Complexity: O(n)

22. Generate Parentheses LeetCode Solution in C++

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, std::move(path), ans);
      path.pop_back();
    }
    if (l < r) {
      path.push_back(')');
      dfs(l, r - 1, std::move(path), ans);
      path.pop_back();
    }
  }
};
/* code provided by PROGIEZ */

22. 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, 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);
    }
  }
}
// code provided by PROGIEZ

22. Generate Parentheses LeetCode Solution in Python

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

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

    dfs(n, n, [])
    return ans
 #code by PROGIEZ