ShahrukhKhan - 1 year ago 71

Java Question

I have this algorithm to generate all combinations of well-formed parentheses.

Can someone explain the core concept of the algorithm? I tried debugging through it, but I still can't seem to grasp the underlying *concept* behind the algorithm.

Additionally, any general advice for how one can come up with such an algorithm for this problem, i.e how did one even get so clever to solve it this way, or what practice one has to do to reach this stage.

Problem:

Givenpairs of parentheses, write a function to generate`n`

all combinations of well-formed parentheses. For example, given, a solution set is:`n = 3`

`“((()))”, “(()())”, “(())()”, “()(())”, “()()()”`

Code:

`public ArrayList<String> generateParenthesis(int n) {`

ArrayList<String> solutions = new ArrayList<String>();

recursion(n, new String(), solutions);

return solutions;

}

private void recursion(int n, String str, ArrayList<String> sol) {

if(str.length() == 2 * n)

sol.add(str);

else {

int left = 0;

int right = 0;

for(int i = 0; i < str.length(); ++i) {

if(str.charAt(i) == '(')

left++;

if(str.charAt(i) == ')')

right++;

}

if(left == right)

recursion(n, str + "(", sol);

else if(right < left) {

if(left < n)

recursion(n, str + "(", sol);

recursion(n, str + ")", sol);

}

}

}

Answer Source

It helps me to see visually how the calls are being stacked. I added a parameter `String depth`

to the call and printed out `depth + str`

on each call, adding four spaces to each depth parameter for a new call. This gives us a good view of the call order.

Here's the code for it:

```
recursion(3, new String(), solutions, "");
//...
private static void recursion(int n, String str, ArrayList<String> sol, String depth) {
System.out.println(depth + str);
//...
if(left == right)
recursion(n, str + "(", sol, depth + " ");
else if(right < left) {
if(left < n)
recursion(n, str + "(", sol, depth + " ");
recursion(n, str + ")", sol, depth + " ");
}
```

And here's what it prints out:

```
(
((
(((
((()
((())
((()))
(()
(()(
(()()
(()())
(())
(())(
(())()
()
()(
()((
()(()
()(())
()()
()()(
()()()
```

Each level of recursion adds another indent to the output. If two outputs are at the same level of indentation, then they were both called from the same level of recursion.

Here's another visual:

Note that each node is a deeper level of recursion and each time a child node comes straight down out of a parent node, it doesn't split into two recursive paths. That is, the parent node only calls `recursion`

once.