Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:
Input: n = 1
Output: [“()”]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { public List<String> generateParenthesis(int n) { List<String> ans = new ArrayList<String>(); backtrack(ans, "", 0, 0, n); return ans; } public void backtrack(List<String> ans, String cur, int open, int close, int max) { if(cur.length() == max * 2) { ans.add(cur); } if(open < max) { backtrack(ans, cur + "(", open + 1, close, max); } if(close < open) { backtrack(ans, cur + ")", open, close + 1, max); } } }
|