C++ String Exercises: Combinations of brackets of pairs of parentheses

Last update on December 20 2024 12:25:55 (UTC/GMT +8 hours)

Write a C++ program to find all combinations of well-formed brackets from a given pair of parentheses.

Example-1:

Input: 2 (given paris of parentheses)

Output: [[]] [][]

Example-2:

Input: 3 (given paris of parentheses)

Output: [[]] [][] [[[]]] [[][]] [[]][] [][[]] [][][]

Sample Solution:

C++ Code:

#include <iostream> // Input/output stream library

#include<algorithm> // Standard library for algorithms such as 'std::sort'
using namespace std; // Using the standard namespace

vector<string> result; // Declare a global vector to store generated parentheses combinations

// Function to generate valid parentheses combinations recursively
void Parenthesis(int start_bracket, int close_bracket, string curr, int n)
{
    // Base case: if the current combination is of length 2*n, it's a valid combination, so add it to the result
    if(curr.size()==2*n)
    {
        result.push_back(curr);
        return;
    }
    // Recursive calls to generate parentheses combinations
    // If the count of opening brackets is less than 'n', add an opening bracket
    if(start_bracket < n)
    {
        Parenthesis(start_bracket+1, close_bracket, curr+"[", n);
    }
    // If the count of closing brackets is less than the count of opening brackets, add a closing bracket
    if(close_bracket < start_bracket)
    {
        Parenthesis(start_bracket, close_bracket+1, curr+"]", n);
    }
}

// Function to generate all valid combinations of parentheses given 'n' pairs
vector<string> generate_Parenthesis(int n) 
{
    Parenthesis(0, 0, "", n); // Call the Parenthesis function to generate combinations
    return result; // Return the vector containing generated combinations
} 

// Main function
int main()
{
   int n;
   vector<string> result_Parenthesis; // Declare a vector to store the generated parentheses combinations

   n = 2; // Set the number of pairs of parentheses

   cout << "n = " << n << "\n"; 
   result_Parenthesis = generate_Parenthesis(n); // Generate parentheses combinations for 'n'

   // Display generated combinations for 'n' pairs of parentheses
   for (int i = 0; i < result_Parenthesis.size(); i++) {
        std::cout << result_Parenthesis.at(i) << ' ';
     }

   n = 3; // Change the number of pairs of parentheses

   cout << "\n\nn = " << n << "\n"; 
   result_Parenthesis = generate_Parenthesis(n); // Generate parentheses combinations for 'n'

   // Display generated combinations for 'n' pairs of parentheses
   for (int i = 0; i < result_Parenthesis.size(); i++) {
        std::cout << result_Parenthesis.at(i) << ' ';
     } 
   return 0; // Return 0 to indicate successful completion
}

Sample Output:

n = 2
[[]] [][]

n = 3
[[]] [][] [[[]]] [[][]] [[]][] [][[]] [][][]

Flowchart:

C++ Code Editor:

Click to Open Editor

Contribute your code and comments through Disqus.

Previous C++ Exercise: Find the longest common prefix from a array of strings.