This problem is a typical backtracking solution problem, we need a recursive method as helper, the following is my first solution, which is not very good, because the quick conditions are too many.
private List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { helper(n, "", 0); return res; } private void helper(int n, String s, int count){ if(s.length()>n*2 || count>n||count<0) return; if(s.length()==n*2&&count==0){ res.add(s.toString()); return; } helper(n, s+'(', count+1); helper(n, s+')', count-1); }
Following is a better solution:
private List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { helper(n, "", 0, 0); return res; } private void helper(int n, String s, int left, int right){ if(s.length()==n*2){ res.add(s.toString()); return; } if(left<n) helper(n, s+'(', left+1,right); if(left>right) helper(n, s+')', left, right+1); }