22. 括号生成【中等】
题解“排列” 类型的题要想到 回溯法
利用左右括号的数目解题是这题最好理解的一种解法：
- 左括号数目
- 右括号数目<左括号数目
添加“）” - 终止条件
（1）右括号数目>左括号数目，这时肯定不是有效括号了，返回
（2）右括号数目==左括号数目==n，完成一组括号排列，返回 - 回溯的时候删掉末尾的括号，重来
class Solution {
private Listres=new ArrayList<>();
public List generateParenthesis(int n) {
backtracking(n,0,0,"");
return res;
}
public void backtracking(int n,int left,int right,String str){
if(right>left)
return;
else if(right==n&&left==n){
res.add(str);
return;
}
if(left
时间复杂度：
O
(
4
n
/
n
)
O(4^n/sqrt{n})
O(4n/n
)
空间复杂度：
O
(
n
)
O(n)
O(n)，最多递归2n次，递归栈所需的空间
