数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
解法一：递归 教会我程序是一步步完善的，有时候不要想着一蹴而就
List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { generate(0, 0, n, ""); return res; } void generate(int left, int right, int n, String str) { // TODO 自动生成的方法存根 if (left == n && right == n) { res.add(str); return; } if (left < n) generate(left + 1, right, n, str + "("); if (right < left && right < n) generate(left, right + 1, n, str + ")"); }
解法二：暴力求解也行，就是加了个对数据的检验 实时检查指的是在数据还没有完全生成的时候，每次添加做一个检查；还是做一个功能包，就是等数据都生成好了，做一个检查
public List<String> generateParenthesis(int n) { List<String> combinations = new ArrayList<String>(); generateAll(new char[2 * n], 0, combinations); return combinations; } public void generateAll(char[] current, int pos, List<String> 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; } }
解法三：
原文：https://www.cnblogs.com/xiaoming521/p/14867480.html