Analysis of time complexity
taher-mulla
302
RecursionInterview

I have written this code for problem 22. Generate Parentheses, this is a Medium-Easy problem.

The solution says the time complexity is different I feel it is O(n^2) as at each step in the recurssion we have only 2 options. and the height of the tree will be 2n.

This is my code:

class Solution {
    List<String> ans = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        
        
        dfs(n, 0, 0, new StringBuilder());
        return ans;
        
    }
    public void dfs(int n, int open, int close, StringBuilder sb){
        // System.out.println("sb : "+sb.toString());
        if(open>n) {
            sb.deleteCharAt(sb.length()-1);
            return;
        }
        if(close<-n) {
            sb.deleteCharAt(sb.length()-1);
            return;
        }
        
        if(open<Math.abs(close)) {
            sb.deleteCharAt(sb.length()-1);
            return;
        }
        
        if(sb.length()==n*2)  {
            ans.add(sb.toString()); 
            sb.deleteCharAt(sb.length()-1);
            return;
        }
        
        dfs(n, open+1, close, sb.append("("));
        dfs(n, open, close-1, sb.append(")"));
        
        if(sb.length()>0)
            sb.deleteCharAt(sb.length()-1);
        return;
        
    }
}
Comments (0)