Generating All Combinations Of Balanced Parenthesis

Parent_Sack

Problem Statement : Given a length of a string containing an equal number of opening and closing parenthesis, generate all valid strings.

Example of string containing balanced parenthesis :
For a string of length 2, the only combination is ( ).
For a string of length 4 the combinations are ( ) ( ) and ( ( ) ).

Idea : To generate all the valid strings containing balanced parenthesis, we use a recursive algorithm.
This algorithm keeps track of the number of opening and a closing parenthesis that are added to the string.
If the sum of an opening and a closing parenthesis is the same as the length of the string, we print the generated string, Else we recursively append an opening parenthesis followed by a closing parenthesis to the string.



Algorithm : Generate (String result, int open, int close, int pairs)

0.    If the sum of an opening and a closing parenthesis equals pairs then
          Print the result string.
1.    Else
2.       If the count of opening parenthesis is less than pairs then,
              Append an opening parenthesis to the string.
              i.e Call Generate ( result + “(", open + 1, close, pairs )).
3.       If the count of closing parenthesis is less than the count of opening parenthesis then,
              Append a closing parenthesis to the string.
              i.e Call Generate ( result + “)", open, close + 1, pairs )).


Python

Python : Generating all strings containing balanced parenthesis.


Java

Java : Generate and print all combinations of a string containing balanced parenthesis.


C++ : Printing all strings containing balanced parenthesis.

#include<iostream>
#include<string>

using namespace std;
int cnt;

// Below function recursively generates strings with balanced parenthesis.
void Generate (string result, int open, int close, int pairs) {

     // If the sum of the opening and closing parenthesis is same as the number of pairs,
     // the we have got a valid string.
     if (open + close == 2 * pairs) {
        cnt++;
        cout << "String " << cnt << " : " << result << endl;
     } else {
        if (open < pairs) {
           Generate (result + "(", open + 1, close, pairs);
        }
        // A closing parenthesis should always come after an opening parenthesis and should always
        // be less than the count of the opening parenthesis already present in the result string
        // before it gets appended.
        if (close < open) {
           Generate (result + ")", open, close + 1, pairs);
        }   
     }   
}

int main() {

    for (int pairs=0; pairs<=3; pairs++) {
        string result ("");
        cnt = 0;
        cout << "\nString(s) with balanced parenthesis of length " << 2*pairs << endl;  
        Generate (result, 0, 0, pairs);
        cout << "Total Strings : " << cnt << endl;
    }   
    return 0;
}

Output

String(s) with balanced parenthesis of length 0
String 1 : 
Total Strings : 1

String(s) with balanced parenthesis of length 2
String 1 : ()
Total Strings : 1

String(s) with balanced parenthesis of length 4
String 1 : (())
String 2 : ()()
Total Strings : 2

String(s) with balanced parenthesis of length 6
String 1 : ((()))
String 2 : (()())
String 3 : (())()
String 4 : ()(())
String 5 : ()()()
Total Strings : 5
Copyright (c) 2020-2021, Algotree.org.
All rights reserved.