public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<String>();
generateOneByOne("", list, n, n);
return list;
}
public void generateOneByOne(String sublist, List<String> list, int left, int right){
if(left > right){
return;
}
if(left > 0){
generateOneByOne( sublist + "(" , list, left1, right);
}
if(right > 0){
generateOneByOne( sublist + ")" , list, left, right1);
}
if(left == 0 && right == 0){
list.add(sublist);
return;
}
}
Java DFS way solution


Thanks for your idea, I rewrite a little bit, basically simplify the logic in comparing left and right.
For other readers, this is a topdown recursion solution. AFAIK, this is faster than the bottomup recursion solution.public List<String> generateParenthesis(int n) { List<String> result = new LinkedList<String>(); if (n > 0) generateParenthesisCore("", n, n, result); return result; } private void generateParenthesisCore(String prefix, int left, int right, List<String> result) { if (left == 0 && right == 0) result.add(prefix); // Has left Parenthesis if (left > 0) generateParenthesisCore(prefix+'(', left1, right, result); // has more right Parenthesis if (left < right) generateParenthesisCore(prefix+')', left, right1, result); }


@Jason_Weng said in Java DFS way solution:
topdown recursion solution. AFAIK, this is faster than the bottomup
Hi @Jason_Weng Why is it a "topdown" recursion rather than the bottomup? Many thanks!


nice explanation, up vote yours! Here is my solution, similar to yours.
class Solution { public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<String>(); if (n <= 0) { return res; } dfs(res, "", n, 0); return res; } public void dfs(List<String> res, String s, int n, int count) { if (n == 0 && count == 0) { res.add(s); return; } if (n < 0) { return; } if (count < 0) { return; } dfs(res, s + "(", n  1, count + 1); dfs(res, s + ")", n, count  1); return; } }