Print all Combinations of Balanced Parentheses in Python

Shape Image One

Print all Combinations of Balanced Parentheses in Python

Problem Statement

Print all the valid parentheses combinations for the given number. Or, generate balanced parentheses using any programming languages like C/C++, Python, Java…

(This was one of the coding questions asked in the OVH cloud coding interview. )

Examples

Example 1:

Input:

n = 2 (number of parenthesis)

Output:

(())
()()

Example 2:

Input:

n = 3 (number of parenthesis)

Output:

((()))
(()())
(())()
()(())
()()()

Explanation

For any valid parentheses, if you traverse from left to right, at any moment, the number of the right parenthesis “)” can not exceed the number of left parentheses “(“.

If the number of left parentheses and right parentheses are the same, there should be a left parenthesis next.

If you understand the above points, it is easy to solve this problem using recursion programming.

Python Code to Print all Valid Balanced Parentheses

#function to print all the valid parenthesis
#using recursion
def printValidPar(left, right, out):
  if right==0:
    return

  elif left==0:
    print(out+right*")")

  elif left==right:
    printValidPar(left-1, right, out+"(")

  else:
    printValidPar(left-1, right, out+"(") 
    printValidPar(left, right-1, out+")") 


#driver function
def validPar(n):
  printValidPar(n,n,"")


validPar(4)

If you understand the logic you can implement it using any general-purpose programming languages like C/C++, Java or Python.

Explanation:

The left and right are the variables to count the number of left and right parentheses remaining respectively.

Variable out is used to store the valid parentheses sequence.

Output:

(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

What’s next?

Sometimes, in coding challenges, you will be asked to count the number of valid possible parentheses. You need to tweak a couple of lines of code. Instead of printing balanced parenthesis, use out as a counter.

Check 50+ interview coding questions for practice.

Let me know if you find any difficulty in solving this problem to print all combinations of balanced parentheses in Python.

1 Comment

  1. def return_balanced_parantheses(string):
    initial_len = len(string)

    while ‘()’ in string:
    string = string.replace(‘()’, ”)

    final_len = len(string)

    return (initial_len – final_len) / 2

    # How is this code buddy?

Leave a Reply

Your email address will not be published. Required fields are marked *