GENERATE PARENTHESES这篇文章讲解了如何使用Depth First Search
,即DFS
算法生成所有有效的括号组合:
void generateParentheses(int n) {
dfs("", n, n);
}
void dfs(String s, int left, int right) // build the set of solutions using DFS approach
{
if(left == 0 && right == 0) // BASE CASE: there is no more parentheses to add? we have a solution!
System.out.println(s);
if(left > 0) // while we have left parentheses to add, just add them
dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added
if(right > left) // We are gonna add a right parentheses if we have more right parentheses than left ones
dfs(s + ")", left, right - 1);
}
由此我也总结了一下DFS
算法:
(1)DFS
算法也是使用递归来解决问题;
(2)
if(left == 0 && right == 0) // BASE CASE: there is no more parentheses to add? we have a solution!
System.out.println(s);
上述代码是递归的终止条件。
(3)
if(left > 0) // while we have left parentheses to add, just add them
dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added
if(right > left) // We are gonna add a right parentheses if we have more right parentheses than left ones
dfs(s + ")", left, right - 1);
每调用一次dfs()
函数,会为字符串添加(
或)
。
if(left > 0) // while we have left parentheses to add, just add them
dfs(s + "(", left - 1, right); // we call our function recursively with a left parentheses added
会递归地生成当前位置是(
的所有情况。if(right > left)
分支则会生成当前位置是)
的所有情况。