Generating All Combinations Of Balanced Parenthesis
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