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

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

## Comment

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.