22. Generate Parentheses java solutions

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:

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

Subscribe to see which companies asked this question

 1 public class Solution {
 2     public List<String> generateParenthesis(int n) {
 3         ArrayList<String> ans = new ArrayList<String>();
 4         generate(n,n,ans,"");
 5         return ans;
 6     }
 7     
 8     public void generate(int left, int right, ArrayList<String> ans, String parenth){
 9         if(left == 0 && right == 0){
10             ans.add(parenth);
11             return;
12         }
13         
14         if(left > 0) generate(left-1, right, ans, parenth + "(");
15         if(right > left) generate(left, right-1, ans, parenth + ")");
16     }
17 }