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