LeetCode 22. Generate Parentheses Java Solution And Time Complexity Explanation

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:

1. If number of left parentheses less than n, we can add another left parentheses to the sequence.
2. 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.