Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res=new ArrayList<>();
String curr="";
backtrack(res,curr,0,0,n);
return res;
}
public void backtrack(List<String> res,String curr,int open,int close,int max){
if(curr.length()==max*2){
res.add(curr);
return;
}
if(open<max) backtrack(res,curr+"(",open+1,close,max);
if(close<open) backtrack(res,curr+")",open,close+1,max);
}
}