Recursive methods have good readability, but stack can over flow if the call stack grows too big. Thus, in an interview, requiring to change a recursive approach to an iterative one is not rare.

Another top rated iterative solution has 4 nested loops. This iterative solution is more intuitive, with less loops.

Look at the diagram above. Say the input n == 3. In the 2D array we store the final result at m[0][n]. The starting point m[0][0] contains an empty string. We walk from m[0][0] to m[0][n]. In each step, we can only move down or move from m[a][b] to m[a + 1][b - 1], which is the upper-right cell. When we move down, we append a "(" to the existing strings. When we move to the upper-right cell, we append a ")" to the existing strings.

When we reach cell m[0][n], we get a valid string. There are various paths to the destination cell, figure A and B are two examples.

Then, let's think about what strings are contained in a cell m[a][b]. As is shown in figure C, if there is a upper cell, we append "(" to all strings in the upper cell and add it to m[a][b]. If there is a cell m[a+1][b-1], which is the lower-left cell, we also append ")" to all strings in that cell and add them to m[a][b]. So, we find a way to generate new cells from existing cells. This is where we use dynamic programming.

Figure D shows how we should loop. We traverse the diagonal lines one by one as the pink arrow indicates, from cell 1 to cell 10. Structure of the loop can be:

for (int b = 1; b <= n; b++) {

for (int a = b; a >= 0; a--) {

// generate cell m[a][b-a] from cells m[a-1][b-a] and m[a+1][b-a-1]

}

}

Add the code for initiating m[0][0], and finally returning m[0][n]:

public List<String> generateParenthesis(int n) {

```
List<String>[][] matrix = new List[n + 1][n + 1];
matrix[0][0] = Collections.singletonList("");
for (int b = 1; b <= n; b++) {
for (int a = b; a >= 0; a--) {
matrix[a][b - a] = new ArrayList<String>();
if (a != 0) {
// stepping down from matrix[a-1][b-a]
for (String s : matrix[a - 1][b - a]) {
matrix[a][b - a].add(s + "(");
}
}
if (b != a) {
// stepping upper-right from matrix[a+1][b-a-1]
for (String s : matrix[a + 1][b - a - 1]) {
matrix[a][b - a].add(s + ")");
}
}
}
}
return matrix[0][n];
```

}

Why it works? In short, we can append "(" to an existing string anytime, but we can only append ")" to the string if the number of '(' in the existing string is more then number of ')'. Here is an example: "(((" can be a prefix of a valid string "((()))", but "()))" can't. We can never get a valid string from "()))". By only allowing walking down or upper-right, we are forcing this rule.

Problem 20 forced this rule with a stack, where you can only pop a stack if you previously pushed "(" into it.