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