题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
解法一
思路：
回溯法，用left 和 right记录左括号和右括号的剩余数量。对于左括号只要还可以放入左括号都可以放入，对于右括号，只有右括号剩余数量大于左括号剩余数量才可以放入。
代码：
class Solution {List<String> ans = new ArrayList<>();public List<String> generateParenthesis(int n) {String parenthesis = "";generateParenthesisHelper(n,n,parenthesis);return ans;}public void generateParenthesisHelper(int left,int right,String parenthesis){if(left == 0 && right == 0){ans.add(parenthesis);return;}if(left > 0){parenthesis+='(';generateParenthesisHelper(left-1,right,parenthesis);//恢复之前的状态parenthesis = parenthesis.substring(0, parenthesis.length() - 1);}if(right>left){parenthesis+=')';generateParenthesisHelper(left,right-1,parenthesis);//parenthesis = parenthesis.substring(0, parenthesis.length() - 1);}}
}