Print all combinations of balanced parentheses
The problem are involves generating all possible combinations of balanced parentheses. A balanced parenthesis expression is one in which every opening parenthesis has a corresponding closing parenthesis and they are nested correctly. This problem is often approached using backtracking, a technique used to systematically search through all possible solutions.
Problem Statement
Given a positive integer size
, the task is to print all possible combinations of balanced parentheses
of size size
.
Example
Let's take an example to understand this better. Suppose size
is 3, then the possible combinations of
balanced parentheses of size 3 are:
- "((()))"
- "(()())"
- "(())()"
- "()(())"
- "()()()"
Idea to Solve
To solve this problem, the idea is to use a backtracking approach. We'll maintain two variables, open
and close
, which represent the count of open and close parentheses used so far. We'll start with an
empty string result
and recursively add open and close parentheses while making sure that the
parentheses remain balanced. We'll also set up base cases to terminate the recursion.
Pseudocode
function balancedBracket(result, size, open, close):
if close == size:
print result
return
if open < size:
balancedBracket(result + "(", size, open + 1, close)
if open > close:
balancedBracket(result + ")", size, open, close + 1)
function main():
size = 4
balancedBracket("", size, 0, 0)
main()
Algorithm Explanation
-
balancedBracket(result, size, open, close)
: This function generates and prints all balanced parentheses combinations. It takes four parameters:result
: The current combination being formed.size
: The desired size of balanced parentheses.open
: The count of open parentheses added so far.close
: The count of close parentheses added so far.
-
The base case is when
close
becomes equal tosize
. This means that a valid combination of parentheses has been formed. So, we print theresult
and return. -
If the
open
count is less thansize
, we can add an open parenthesis. So, we recursively callbalancedBracket
with an added open parenthesis, and we increase theopen
count by 1. -
If the
open
count is greater than theclose
count, we can add a close parenthesis. So, we recursively callbalancedBracket
with an added close parenthesis, and we increase theclose
count by 1.
Code Solution
-
1) Print all combinations of balanced parentheses in java
2) Print all combinations of balanced parentheses in c++
3) Print all combinations of balanced parentheses in c#
4) Print all combinations of balanced parentheses in php
5) Print all combinations of balanced parentheses in python
6) Print all combinations of balanced parentheses in ruby
7) Print all combinations of balanced parentheses in scala
8) Print all combinations of balanced parentheses in swift
9) Print all combinations of balanced parentheses in c
10) Print all combinations of balanced parentheses in kotlin
11) Print all combinations of balanced parentheses in node js
12) Print all combinations of balanced parentheses in vb.net
13) Print all combinations of balanced parentheses in golang
14) Print all combinations of balanced parentheses in typescript
Time Complexity
The time complexity of this algorithm can be analyzed by observing the recursive tree structure. For each position
in the result string, there are two possibilities: adding an open parenthesis or adding a close parenthesis. This
results in a binary tree with a maximum depth of 2*size
. Therefore, the time complexity is
O(2^(2*size)), which is exponential in terms of the input size.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment