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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
难度:medium
题目:给定n对圆括号,写函数产生其所有格式良好的组合形式。
思路:右边括号数一定不能大于左边,然后利用递归来实现。
Runtime: 1 ms, faster than 100.00% of Java online submissions for Generate Parentheses.
Memory Usage: 27.8 MB, less than 7.34% of Java online submissions for Generate Parentheses.
class Solution { public List<String> generateParenthesis(int n) { List<String> result = new ArrayList<>(); generateParenthesis(0, 0, n, new StringBuilder(), result); return result; } private void generateParenthesis(int left, int right, int n, StringBuilder sb, List<String> result) { if (left < right) { return; } if (left == right && n == left) { result.add(sb.toString()); return; } if (left < n && left >= right) { sb.append("("); generateParenthesis(left + 1, right, n, sb, result); sb.deleteCharAt(sb.length() - 1); } if (right < left) { sb.append(")"); generateParenthesis(left, right + 1, n, sb, result); sb.deleteCharAt(sb.length() - 1); } } }