由一道题理解DFS算法

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)分支则会生成当前位置是)的所有情况。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.