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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

DP method:
First consider how to get the result f(n) from previous result f(0)…f(n-1).

Actually, the result f(n) will be put an extra () pair to f(n-1).

Let the “(” always at the first position, to produce a valid result, we can only put “)” in a way that there will be :

i pairs () inside the extra () and n - 1 - i pairs () outside the extra pair.

Let us consider an example to get clear view:

f(0): “”

f(1): “(“f(0)”)”

f(2): “(“f(0)”)”f(1), “(“f(1)”)”

f(3): “(“f(0)”)”f(2), “(“f(1)”)”f(1), “(“f(2)”)”

So f(n) = “(“f(0)”)”f(n-1) , “(“f(1)”)”f(n-2) “(“f(2)”)”f(n-3) … “(“f(i)”)“f(n-1-i) … “(f(n-1)”)”

Implemented as below:

class Solution {
    public List<String> generateParenthesis(int n) {
        List<List<String>> dp = new ArrayList<>();
        for(int i=0;i<=n;i++){
            List<String> list = new ArrayList<>();
            if(i==0) list.add("");
            else{
                for(int j=0;j<i;j++){
                    for(String s:dp.get(j)){
                        for(String t:dp.get(i-j-1)){
                            list.add("("+s+")"+t);
                        }
                    }
                }
            }
            dp.add(list);
        }
        return dp.get(n);
    }
}