22.括号生成

22.括号生成

22.括号生成

比较容易想到暴力解法，生成所有的括号然后检验是否有效。

public List generateParenthesis(int n) { List combinations = new ArrayList(); generateAll(new char[2 * n], 0, combinations); return combinations; } public void generateAll(char[] current, int pos, List result) { if (pos == current.length) { if (valid(current)) { result.add(new String(current)); } } else { current[pos] = '('; generateAll(current, pos + 1, result); current[pos] = ')'; generateAll(current, pos + 1, result); } } public boolean valid(char[] current) { int balance = 0; for (char c: current) { if (c == '(') { ++balance; } else { --balance; } if (balance < 0) { return false; } } return balance == 0; }

回溯法--只生成有效的括号，

public List generateParenthesis(int n) { List ans = new ArrayList<>(); backtrack(ans,new StringBuilder(),0,0,n); return ans; } public void backtrack(List ans, StringBuilder cur, int open, int close, int max) { if (cur.length() == max*2) { ans.add(cur.toString()); return; } if (open < max) { cur.append('('); backtrack(ans,cur,open+1,close,max); cur.deleteCharAt(cur.length()-1); } if (close < open) { cur.append(')'); backtrack(ans, cur, open, close+1,max); cur.deleteCharAt(cur.length()-1) }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。