博文中会简要介绍Leetcode P0022题目分析及解题思路。
“Generate Parentheses”是一道明显的深度搜索问题，其思路核心是建立具有正确终止条件的DFS，唯一需要注意的是，问题要求生成正确的括号序列，即左右括号要匹配。这个要求可以通过记录当前剩余的待匹配的左括号个数来判断当前是否能够使用右括号。
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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
以下是Java的题解代码实现。
class Solution {
public List<String> generateParenthesis(int n) {
if (n == 0)
return new ArrayList<String>();
if (n == 1)
return Arrays.asList(new String[] {"()"});
this.combine(0, n, new StringBuilder());
return this.combinations;
}
private List<String> combinations = new ArrayList<>();
private void combine(int leftBracketRemain, int leftBracketTotal, StringBuilder sequence) {
if (leftBracketRemain == 0 && leftBracketTotal == 0) {
combinations.add(sequence.toString());
return;
}
char[] options = new char[] {'(', ')'};
for (int itr=0; itr<options.length; ++itr) {
if (options[itr] == '(' && leftBracketTotal > 0) {
sequence.append(options[itr]);
this.combine(leftBracketRemain+1, leftBracketTotal-1, sequence);
sequence.deleteCharAt(sequence.length()-1);
}
if (options[itr] == ')' && leftBracketRemain > 0) {
sequence.append(options[itr]);
this.combine(leftBracketRemain-1, leftBracketTotal, sequence);
sequence.deleteCharAt(sequence.length()-1);
}
}
}
}