题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[

"((()))",

"(()())",

"(())()",

"()(())",

"()()()"

]

解决方法

合法的括号：

1. 左括号在对应右括号的左边 -> 先添加左括号再添加右括号即可保证左括号在右括号的左边
2. 相同数量的左右括号 -> 右括号数量 == 左括号数量
3. 最终形成的字符串长度为n*2，也就是左右括号各n个

根据以上分析使用回溯法

public List
    
      generateParenthesis(int n) {        List
     
       res = new ArrayList<>();        process(res, "", 0, 0, n);        return res;    }    /**     * @param res   结果     * @param str   结果中的一项     * @param open  左括号数量     * @param close 右括号数量     * @param n     生成的括号对数     */    public void process(List
      
        res, String str, int open, int close, int n) {        if (str.length() == n * 2) {            res.add(str);        } else {            if (open < n)                process(res, str + "(", open + 1, close, n);            if (close < open)                process(res, str + ")", open, close + 1, n);        }    }
      
     
    

本文首发：