22. Generate Parentheses

    /*
     * 22. Generate Parentheses 
     * 2015.12.13 by Mingyang
     * 1.长度标准：无
     * 2.可选的范围：只有左括号和右括号，先一直加左边，完了再加右边
     * 3.往前走一步：sb加了，left或right减一
     * 4.后退一步：sb remove
     * 5.特别的case：left和right都为0
     * 6.关于重复：无
     */
     public List<String> generateParenthesis(int n) {
            List<String> res=new ArrayList<String>();
            StringBuffer sb=new StringBuffer();
            dfs(res,sb,n,n);
            return res;
        }
        public void dfs(List<String> res,StringBuffer sb,int left,int right){
            if(left==0&&right==0){
                res.add(sb.toString());
                return;
            }
            if(left>right||left<0||right<0)
              return;
            sb.append(‘(‘);
            dfs(res,sb,left-1,right);
            sb.deleteCharAt(sb.length()-1);
            sb.append(‘)‘);
            dfs(res,sb,left,right-1);
            sb.deleteCharAt(sb.length()-1);
        }