Articles by FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
Articles by FavTutor
No Result
View All Result
Home Data Structures and Algorithms

Generate Parentheses Problem (C++, Java, Python)

Jatin Chanana by Jatin Chanana
January 10, 2024
Reading Time: 6 mins read
Generate Parentheses leetcode problem
Follow us on Google News   Subscribe to our newsletter

Parentheses combinations are a common challenge in programming and mathematics expressions. They help in grouping elements and defining the order of operations. Generating parentheses is one such popular leet code problem. In this article, we will discuss an approach to solving Generating parentheses problem using recursion.

What is the Generate Parentheses Problem?

In the Generate Parentheses problem, we have to generate all the possible combinations of balanced parentheses for a given number n. The goal is to create a valid sequence of opening and closing parentheses.

Let us understand it better with an example:

Input: n = 3

Output: [“((()))” , “(()())”,  “(())()” ,  “()(())”, “()()()” ]

Before moving to an optimized approach, we can look at a straightforward solution. given a total of n pairs, the resulting strings will have a length of 2n, considering each pair contributes an opening and a closing bracket. A brute forarch approach involves recursively generating all strings of length 2n and identifying the balanced ones. 

The process entails exploring each index from 0 to 2n, where at each index i, there are two choices: inserting ‘(‘ or ‘)’. The recursive function is then called for both options. When the string reaches a length of 2n, it is checked for balance. Valid strings are stored in a vector.

Example of Generate Parentheses

Here are the steps to be followed in this approach:

  • First, we will declare a result vector to store balanced strings of length 2*n. 
  • Now we will generate an empty string. Now we will call our recursive function which will help us to fill our result vector with all balanced strings
  • Now we will call our recursive function
  • First of all, we’ll check if the length of our current string is 2*n. If it is, we’ll examine if it’s balanced. If it’s balanced, we’ll include it in the answer list and finish. If it’s not balanced, we’ll stop.
  • If our string isn’t the right length yet, we’ll keep adding parentheses. We’ll call the recursive function twice – once after adding ‘(‘ and once after adding ‘)’ to our current string. It’s like trying different options and going back if needed.
  • At last, we will return our result vector that contains all balanced strings.

The Time Complexity is O((2^(2*n))*n), where n is the number of pairs of parentheses. Because for each index i from 0 to 2*n-1, we’re making two recursive calls. And when we check if the string is balanced, it takes another O(2*n) time for each string. 

The Space Complexity is O((2^(2*n))*n), where n is the number of pairs of parentheses. Because in the worst case, all the strings can be balanced. So we need to store all of them.

Recursive Approach

To solve the Generate Parentheses problem recursively, we start by defining a recursive function. The goal is to explore all possible combinations while ensuring the parentheses remain well-formed.

By optimizing the above approach we can generate all combinations of parenthesis from recursion and by applying some conditions we can obtain the possible combinations of balanced parenthesis.

Below is how to do it step-by-step to be followed for this approach:

  • Base Case: If the counts of opening and closing parentheses equal n, a valid combination is added to the result.
  • Recursive Step 1: If the count of open parentheses is less than n, a new opening parenthesis is added, and the function is called recursively with an incremented count of opening parentheses.
  • Recursive Step 2: If the count of closed parentheses is less than that of open parentheses, a new closing parenthesis is added, and the function is called recursively with an incremented count of closing parentheses.
  • These recursive steps help to explore all possibilities.

C++ Code

Here is the C++ program to generate all the possible combinations of balanced parentheses:

#include <iostream>
#include <vector>
using namespace std;

void generateParenthesis(string p, int left, int right, vector<string>& parens) {
    if (left > 0) {
        generateParenthesis(p + '(', left - 1, right, parens);
    }
    if (right > left) {
        generateParenthesis(p + ')', left, right - 1, parens);
    }
    if (right == 0) {
        parens.push_back(p);
    }
}

int main() {
    vector<string> result;
    int n = 3;
    generateParenthesis("", n, n, result);

    for (const string& s : result) {
        cout << s << endl;
    }

    return 0;
}

Python Code

Below is the Python solutions for Generate Parentheses problem:

def generate_parenthesis(p, left, right, parens):
    if left > 0:
        generate_parenthesis(p + '(', left - 1, right, parens)
    if right > left:
        generate_parenthesis(p + ')', left, right - 1, parens)
    if right == 0:
        parens.append(p)

def main():
    result = []
    n = 3
    generate_parenthesis("", n, n, result)

    for s in result:
        print(s)

if __name__ == "__main__":
    main()

Java Code

You can implement it in JavaScript as well:

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {
    public static void generateParenthesis(String p, int left, int right, List<String> parens) {
        if (left > 0) {
            generateParenthesis(p + '(', left - 1, right, parens);
        }
        if (right > left) {
            generateParenthesis(p + ')', left, right - 1, parens);
        }
        if (right == 0) {
            parens.add(p);
        }
    }

    public static void main(String[] args) {
        List<String> result = new ArrayList<>();
        int n = 3;
        generateParenthesis("", n, n, result);

        for (String s : result) {
            System.out.println(s);
        }
    }
}

Output:

((()))
(()())
(())()
()(())
()()()

The time complexity for the recursion approach to generate all the possible combinations of balanced parentheses is O(4^n / sqrt(n)), where “n” is the number of pairs of parentheses. This complexity arises from the fact that for each position in the result string, we have two choices (open or close), and we do this for a total of 2 * n positions. 

The space complexity is O(4^n / sqrt(n)), as well. This is because the recursive calls can go as deep as 2 * n, and at each level, we generate two branches.

Conclusion

In this article, we’ve discussed the generate parentheses leetcode problem with the brute force approach and optimized Approach along with their implementations. We have also discussed the complexities of both approaches. You can try out more similar problems to keep improving.

ShareTweetShareSendSend
Jatin Chanana

Jatin Chanana

I am Jatin, a final-year undergraduate student with a keen interest in the field of software development. I possess a strong academic background and a deep passion for Data Structures, Algorithms, and Web Development.

RelatedPosts

validate ip address

Validate IP Address Problem ( C++, JAVA, Python)

April 3, 2025
Shortest Palindrome Problem

Shortest Palindrome Problem ( C++, JAVA, Python)

April 4, 2025
Zigzag Conversion Problem

Zigzag Conversion Problem (C++, Java, Python)

April 4, 2025
Next Right Pointers In Each Node

Populating Next Right Pointers In Each Node (with code)

March 27, 2024
Coin Change II

Coin Change II Problem (C++, Java, Python)

April 7, 2025

About FavTutor

FavTutor is a trusted online tutoring service to connects students with expert tutors to provide guidance on Computer Science subjects like Java, Python, C, C++, SQL, Data Science, Statistics, etc.

Categories

  • AI News, Research & Latest Updates
  • Trending
  • Data Structures
  • Web Developement
  • Data Science

Important Subjects

  • Python Assignment Help
  • C++ Help
  • R Programming Help
  • Java Homework Help
  • Programming Help

Resources

  • About Us
  • Contact Us
  • Editorial Policy
  • Privacy Policy
  • Terms and Conditions

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.

No Result
View All Result
  • AI News
  • Data Structures
  • Web Developement
  • AI Code Generator
  • Student Help
  • Main Website

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.