# *Java* Easy to understand recursive DP method with explanations

• For each valid parenthesis, there must be a pair whose right parenthesis is at the rightmost location. Thus, a valid parenthesis has to be of the following form:

``````* ( * )
``````

where `*` denotes the remaining parentheses which are don't yet know (`*` can be empty, i.e., with 0 pair of parenthesis). However, we do know the following two important facts:

• both two `*` are valid parentheses;
• they don't overlap at all! (a pair has to be either on the left side or inside `()`, but cannot be the case where `(` is on the left side and `)` is inside `()`)

If we put `i` parentheses inside `()`, there are `n-i-1` to be put on the left side. This gives us a recursive formula as below:

``````P(n) = P(n-i-1) x P(i)
``````

where `P(n)` are all valid parentheses with `n` parentheses.

To this point, we are done with the algorithm, the only remaining task is coding, which is given below:

``````public List<String> generateParenthesis(int n) {
List<String>[] lists = new LinkedList[n+1]; // store all P(k)'s for k=0,1,...,n
return helper(n, lists);
}

private List<String> helper(int n, List<String>[] lists) {
if(lists[n]!=null) return lists[n]; // if computed, reuse
if(n<=0) {
return lists[0];
}
else if(n==1) {
return lists[1];
}
// the following simply implements the recursive formula derived above
for(int i=0; i<=n-1; i++) {
List<String> left = helper(n-i-1, lists);
List<String> inside = helper(i, lists);
for(String str1 : left) {
for(String str2 : inside) {
res.add(str1 + "(" + str2 + ")");
}
}
}
lists[n] = res; // store computed results for reuse
return res;
}
``````

If you are interested in my other posts, please feel free to check my Github page here: https://github.com/F-L-A-G/Algorithms-in-Java

• Elegant design!!

• dose this:"List<String>[] lists=new LinkedList<String>[n+1]" worked?

• @lovebabymao it should work, but there is a warning since List is a raw type and you are supposed to specify the data type.

• I really like ur post, thanks a lot!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.