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 )).


cnt = 0 

# Below function recursively generates strings with balanced parenthesis.
def Generate (result, _open, _close, _pairs):

     global cnt 
     # 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 += 1
        print("String " + str(cnt) + " : " + str(result))
     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);

def main():

    global cnt 
    for _pairs in range (1, 4): 
        result = ""
        print ("\nString(s) with balanced parenthesis of length " + str(2 * _pairs))
        cnt = 0 
        Generate (result, 0, 0, _pairs);
        print ("Total Strings : " + str(cnt));

if __name__ == "__main__":
    main()

Output


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
#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
class Parenthesis {

    public int cnt;
    // Below function recursively generates strings with balanced parenthesis.
    public 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++;
            System.out.println( "String " + cnt + " : " + result);
         } 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);
            }
         }
    }   
    
    public static void main (String [] args) {
    
        Parenthesis p = new Parenthesis();

        for (int pairs=0; pairs<=3; pairs++) {
            String result = "";
            p.cnt = 0;
            System.out.println ("\nString(s) with balanced parenthesis of length " + 2 * pairs);  
            p.Generate (result, 0, 0, pairs);
            System.out.println ("Total Strings : " + p.cnt);
        }
    }   
}

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) 2019-2022, Algotree.org.
All rights reserved.