博客

 //括号生成
    //回溯法
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n == 0) {
            return result;
        }
        backResult(result,new StringBuffer(),0,0,n);
        return result;
    }

    //cur代表当前字符串
    //left代表当前左括号数量
    //right代表当前右括号数量
    private void backResult(List<String> result, StringBuffer cur, int left, int right, int n) {
        if (cur.length() == 2*n) {
            result.add(cur.toString());
            return;
        }
        //左括号不够加左括号然后递归最后恢复现场
        if (left<n) {
            cur.append("(");
            backResult(result,cur,left+1,right,n);
            cur.deleteCharAt(cur.length()-1);
        }
        //右括号没左括号数量多就加右括号，然后递归最后恢复现场
        if (right<left) {
            cur.append(")");
            backResult(result,cur,left,right+1,n);
            cur.deleteCharAt(cur.length()-1);
        }
    }