Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses of length 2*n.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
Make sure the returned list of strings are sorted.
Method:
Add left parentheses first, then right.
Solution:
Time: O(2^n) Space: O(2^n)
public class Solution { public ArrayList<String> generateParenthesis(int A) { ArrayList<String> result = new ArrayList<>(); StringBuilder sb = new StringBuilder(); helper(result, sb, A, A); return result; }
private void helper(ArrayList<String> result, StringBuilder sb, int left, int right) { if (left == 0 && right == 0) { result.add(sb.toString()); return; } if (left > 0) { sb.append('('); helper(result, sb, left - 1, right); sb.deleteCharAt(sb.length() - 1); } if (right > 0 && right > left) { sb.append(')'); helper(result, sb, left, right - 1); sb.deleteCharAt(sb.length() - 1); } } }