Leetcode 22 Generate Parentheses

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 1: use dfs or back tracking. Left & Right mean how many open and close parentheses left to place. Remember left>0 condition.

 public class Solution {  
   public List<String> generateParenthesis(int n) {  
     StringBuilder one=new StringBuilder();  
     List<String> res=new ArrayList<>();  
     if (n<=0) return res;  
     dfs(n,n,one, res);  
     return res;  
   }  
   private void dfs(int left, int right, StringBuilder one, List<String> res) {  
     if (left==0 && right==0) res.add(one.toString());  
     else {  
       if (left>0) {  
         one.append('(');  
         dfs(left-1,right,one,res);  
         one.deleteCharAt(one.length()-1);  
       }  
       if (left<right) {  
         one.append(')');  
         dfs(left,right-1,one,res);  
         one.deleteCharAt(one.length()-1);  
       }  
     }  
   }  
 }