Generate all Combinations of Balanced Parentheses in Python

October 14, 2022

All Combinations of Balanced Parentheses in Python

Here on this page, we will learn how to generate All Combinations of Balanced Parentheses in Python programming language. We are given an integer N representing the number of pairs of parentheses, the task is to generate all combinations of well-formed(balanced) parentheses.

Algorithm ( Method 1 )

Create a recursive function that accepts a string say s, count of opening brackets say, o and count of closing brackets say, c and the value of n.
If the value of the opening bracket and closing bracket is equal to n then print the string and return.
If the count of the opening bracket is greater than the closing bracket, then call the function recursively.
If the count of the opening bracket is less than n then call the function recursively.

Python Code

Run

def printParenthesis(str, n):
	if n > 0:
		_printParenthesis(str, 0, n, 0, 0)
	return


def _printParenthesis(str, pos, n, open, close):

	if close == n:
		for i in str:
			print(i, end="")
		print()
		return
	else:
		if open > close:
			str[pos] = '}'
			_printParenthesis(str, pos + 1, n, open, close + 1)
		if open < n:
			str[pos] = '{'
			_printParenthesis(str, pos + 1, n, open + 1, close)


n = 3
string = [""] * 2 * n
printParenthesis(string, n)

Output

{}{}{}
{}{{}}
{{}}{}
{{}{}}
{{{}}}

Algorithm ( Method 2 )

In this method, we write the simple code for the above algorithm.

Run

def generateParenthesis(n, Open, close, s, ans):

    if Open == n and close == n:
        ans.append(s)
        return

    if Open < n:
        generateParenthesis(n, Open + 1, close, s + "{", ans)

    if close < Open:
        generateParenthesis(n, Open, close + 1, s + "}", ans)


n = 3
ans = []
generateParenthesis(n, 0, 0, "", ans)
for s in ans:
    print(s)