**Time complexity = O(2^n)**

As in each position, there're 2 candidates to put: '(' or ')'. For n positions, there're 2^n possibilities.

**JAVA Code:**

```
public List<String> generateParenthesis(int n) {
List<String>res = new LinkedList<String>();
DFS("", n, n, res);
return res;
}
void DFS(String curr, int left, int right, List<String> res) {// left, right: the remaining amount of '(', ')'
if (left == 0 && right == 0) {
res.add(curr);
return;
}
if (left > 0)// Check '(': 1) still has '(': '(' can be added without precondition check
DFS(curr + "(", left-1, right, res);
if (right > 0 && left < right)// Check ')': 1) still has ')'; 2) existing '(' is more than ')'
DFS(curr + ")", left, right-1, res);
}
```