22. Generate Parentheses Leetcode Java

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Solution:
Recursion and backtracking.
Use two variables l and r to track the remaining amount of left and right parentheses. During the recursion, either left or right can be put into the string depends on the current situation. Several rules must be followed. First, if now l==r, we can't put right one, so r must >= l. Second, l and r must both >=0, so if l==0, only right one can be append to the string. Third: the base case: when l==r==0, add the string to the result set.
Time complexity: Result-Oriented.

 public List<String> generateParenthesis(int n) {  
     List<String> res=new ArrayList<String>();  
     if(n==0) return res;  
     StringBuilder sb=new StringBuilder();  
     helper(n,n,sb,res);  
     return res;  
   }  
   public void helper(int l,int r, StringBuilder sb, List<String> res){  
     if(l==0 && r==0){  
       res.add(sb.toString());  
       return;  
     }  
     if(r<l) return;  
     if(l>0){  
       sb.append('(');  
       helper(l-1,r,sb,res);  
       sb.deleteCharAt(sb.length()-1);  
     }  
     if (r>0){  
       sb.append(')');  
       helper(l,r-1,sb,res);  
       sb.deleteCharAt(sb.length()-1);  
     }  
   }