Issue with tracing down the array in Java recursion function

Question

I have an issue with recursion in Java. The question is as such:

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:

The code for the above problem is recursive and is as mentioned below:

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);
    }
}

I have been able to trace the program upto a particular point, but I am unable to trace it down totally.

if 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    |
|        |
|        |
|________|

how would the program work after what I have mentioned above? Can someone help me tracing it? Thanks.

Answer 1

From where you left off:

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

If you're using eclipse or any other IDE, it should be easy to set a breakpoint and go through how your program runs line by line (showing all your variables and how they change). If you haven't learned debugging yet, I would encourage you to google it and learn how to debug programs.

What your program is actually doing:

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)