Table of Contents
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. )
Example 1:
Input: n = 2 (number of parenthesis) Output: (()) ()()
Example 2:
Input: n = 3 (number of parenthesis) Output: ((())) (()()) (())() ()(()) ()()()
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.
#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.
I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.
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?