Generate Parentheses

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:
1. [
2. "((()))",
3. "(()())",
4. "(())()",
5. "()(())",
6. "()()()"
7. ]

Solution:
1. public class Solution {
2. public List generateParenthesis(int n) {
3. List res = new ArrayList();
4. helper(n, 0, 0, "", res);
5. return res;
6. }
7. 8. private void helper(int n, int left, int right, String sol, List res) {
9. if (right == n) {
10. res.add(sol);
11. return;
12. }
13. 14. if (left < n) {
15. helper(n, left + 1, right, sol + "(", res);
16. }
17. 18. if (right < left) {
19. helper(n, left, right + 1, sol + ")", res);
20. }
21. }
22. }