For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
解题思路:
i 位置为( 或者 ) 取决于 目前左括号的数目和右括号的数目.
leftN < n 时,此位置可以为左括号
rightN < leftN && rightN < n时,此位置可以为右括号.
public ListgenerateParenthesis(int n) { List res = new ArrayList (); getAllSolution(0,0,n,"",res); return res; } public void getAllSolution(int leftN, int rightN, int n,String s, List solution){ if(leftN == n && rightN == n){ solution.add(s); return; } if(leftN < n){ getAllSolution(leftN+1, rightN, n, s + "(", solution); } if(rightN < n && rightN < leftN){ getAllSolution(leftN, rightN + 1, n, s + ")", solution); } }
No comments:
Post a Comment