java - 在 Java 递归函数中追踪数组的问题

Question

我对 Java 中的递归有疑问。问题是这样的:

给定 n 对括号，编写一个函数来生成格式正确的括号的所有组合。

例如，给定n = 3，一个解集是:

上述问题的代码是递归的，如下所示:

public List<String> generateParenthesis(int n) {
    ArrayList<String> result = new ArrayList<String>();
    dfs(result, "", n, n);
    return result;
}

public void dfs(ArrayList<String> result, String s, int left, int right){
    if(left > right)
        return;

    if(left==0&&right==0){
        result.add(s);
        return;
    }

    if(left>0){
        dfs(result, s+"(", left-1, right);
    }

    if(right>0){
        dfs(result, s+")", left, right-1);
    }
}

我已经能够将程序追踪到一个特定的点，但我无法完全追踪到它。

如果 n=2

left=2;right=2;
result="(())", 
__________
| s=""   |
| l=2    |
| r=2    |
|        |
|        |
|________|
    |
    V
__________  
| s=(    |
| l 1    |
| r 2    |
|        |
|        |
|________|
    |
    V
__________
| s=((   |
| l 0    |
| r 2    |
|        |
|        |
|________|
    |
    V
__________
| s=(()  |
| l 0    |
| r 1    |
|        |
|        |
|________|
    |
    V
__________  
| s= (())|
| l=0    |
| r=0    |
|        |
|        |
|________|

在我上面提到的之后程序会如何工作？有人可以帮我追踪吗？谢谢。

Answer 1

从你离开的地方开始:

__________
| s=(    |
| l=1    |
| r=2    |
|        |
|        |
|________|
    |
    V
__________  
| s=()   |
| l 1    |
| r 1    |
|        |
|        |
|________|
    |
    V
__________
| s=()(  |
| l 0    |
| r 1    |
|        |
|        |
|________|
    |
    V
__________
| s=()() |
| l 0    |
| r 0    |
|        |
|        |
|________|

如果您使用的是 eclipse 或任何其他 IDE，设置断点并逐行检查程序的运行方式(显示所有变量及其变化)应该很容易。如果您还没有学习过调试，我鼓励您用谷歌搜索并学习如何调试程序。

你的程序实际上在做什么:

left (l=1, r=2)
  left (l=0, r=2)
    right (l=0, r=1)
      right (l=0, r=0)
        add result to s (l=0, r=0)
    *here you break out of 3 recursive functions and values of l,r reset to (l=1, r=2)*
  right (l=1, r=1)
    left (l=0, r=1)
      right (l=0, r=0)
      add result to s (l=0, r=0)