题目描述
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[“((()))”, “(()())”, “(())()”, “()(())”, “()()()”]
解决方法
合法的括号：
左括号在对应右括号的左边 -> 先添加左括号再添加右括号即可保证左括号在右括号的左边
相同数量的左右括号 -> 右括号数量 == 左括号数量
最终形成的字符串长度为 n *2，也就是左右括号各 n 个
根据以上分析使用回溯法
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
process(res, “”, 0, 0, n);
return res;
}
/**
* @param res 结果
* @param str 结果中的一项
* @param open 左括号数量
* @param close 右括号数量
* @param n 生成的括号对数
*/
public void process(List<String> 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);
}
}
本文首发：https://lierabbit.cn/2018/09/…