So I have tried two different approach, the first one is the normal backtracking solution, which takes 2ms.

And I came up with the solution below.

The idea is to get the result of one less pair of parentheses, then insert another into each possible location.

```
public List<String> generateParenthesis(int n) {
List<String> rt = new ArrayList();
if(n == 0){
rt.add("");
return rt;
}
List<String> sub = generateParenthesis(n-1);
for(String item : sub){
for(int i = 0 ; i <= item.length() / 2; i++){
// insert another pair
String newStr = item.substring(0, i) +"()" + item.substring(i);
if(!rt.contains(newStr)){
rt.add(newStr);
}
}
}
return rt;
}
```

This

It took 25ms. Could anyone help me to understand what's the time complexity here?