LC22.java

public class LC22 {
    
// solve called for :           left : 0    right : 0
// solve called for : (         left : 1    right : 0
// solve called for : ((        left : 2    right : 0
// solve called for : (((       left : 3    right : 0
// solve called for : ((()      left : 3    right : 1
// solve called for : ((())     left : 3    right : 2
// solve called for : ((()))    left : 3    right : 3
// solve called for : (()       left : 2    right : 1
// solve called for : (()(      left : 3    right : 1
// solve called for : (()()     left : 3    right : 2
// solve called for : (()())    left : 3    right : 3
// solve called for : (())      left : 2    right : 2
// solve called for : (())(     left : 3    right : 2
// solve called for : (())()    left : 3    right : 3
// solve called for : ()        left : 1    right : 1
// solve called for : ()(       left : 2    right : 1
// solve called for : ()((      left : 3    right : 1
// solve called for : ()(()     left : 3    right : 2
// solve called for : ()(())    left : 3    right : 3
// solve called for : ()()      left : 2    right : 2
// solve called for : ()()(     left : 3    right : 2
// solve called for : ()()()    left : 3    right : 3
// answer -> ((())) (()()) (())() ()(()) ()()() 
  
     static List<String> ans;

    public static void main(String[] args) {
        generateParenthesis(3);

        for (String c:ans)
            System.out.print(c + " ");
    }

    public static List<String> generateParenthesis(int n) {

        ans = new ArrayList<>();
        solve("",0,0,n);
        return ans;

    }
    
    private static void solve(String str,int left,int right,int n){

        System.out.println("solve called for : " + str + " left : " + left + " right : " + right);
        if(str.length()==2*n)
            ans.add(str);

        if(left<n){
            String temp1 = str;
            temp1+="(";
            solve(temp1,left+1,right,n);
        }

        if(right<left){
            String temp1 = str;
            temp1 += ")";
            solve(temp1,left,right+1,n);
        }

    }
}