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

1. 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.

2. The base case is when close becomes equal to size. This means that a valid combination of parentheses has been formed. So, we print the result and return.

3. If the open count is less than size, we can add an open parenthesis. So, we recursively call balancedBracket with an added open parenthesis, and we increase the open count by 1.

4. If the open count is greater than the close count, we can add a close parenthesis. So, we recursively call balancedBracket with an added close parenthesis, and we increase the close 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.