Generating all possible combinations of balanced parentheses is a common interview problem & is found in websites like LeetCode & GeeksForGeeks.**Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.**

```
Input: n = 1
Output: ["()"]
```

```
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
```

We are using backtracking to solve this problem. There are two cases where we can proceed to the next recursive step:

- If number of left parentheses less than n, we can add another left parentheses to the sequence.
- If right parentheses count is less than left parentheses count, we can add another right parentheses.

If size of sequence is 2*n, we got a valid sequence. Otherwise if we can’t proceed to next step due to failure of above conditions, we need to bracktrack from there.

Here is the Java code solution for this:

class Solution { public List<String> generateParenthesis(int n) { List<String> result = new ArrayList<>(); generateParenthesis(result, "", 0, 0, n); return result; } public void generateParenthesis(List<String> result, String str, int leftCount, int rightCount, int n){ if(str.length() == 2*n){ result.add(str); } if(leftCount < n){ generateParenthesis(result, str + "(", leftCount + 1, rightCount, n); } if(leftCount > rightCount){ generateParenthesis(result, str + ")", leftCount, rightCount + 1, n); } } }

Lets’ calculate worst time complexity of the above solution. In each step, at max we can go to two recursive options, condition 1 & condition 2.

```
T(n) = T(n-1) + T(n-1)
= 2 * T(n-1)
= 2 * (2 *T(n-2))
= 2^2 T(n-2)
= 2^2 (2 * T(n-3))
= 2^3 T(n-3)
= 2^n T(1)
= 2^n * 1
= 2^n
```

So worst time complexity of the backtracking solution for generate parentheses problem is O(2^n) which is exponential.