题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例： 输入：n = 3 输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

暴力算法+递归生成所有可能性

class Solution { 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 { //递归的生成所有可能性 //位置pos的地方 既可以是（ 也可以是） 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; } }

回溯

class Solution { public List<String> generateParenthesis(int n) { List<String> ans = new ArrayList<String>(); backtrack(ans, new StringBuilder(), 0, 0, n); return ans; } public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) { if (cur.length() == max * 2) { ans.add(cur.toString()); return; } // if (open < max) { cur.append('('); //探索了所有curr开头的字符串的可能 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); } } }

递归

class Solution { ArrayList[] cache = new ArrayList[100]; public List<String> generate(int n) { if (cache[n] != null) { return cache[n]; } ArrayList<String> ans = new ArrayList<String>(); if (n == 0) { ans.add(""); } else { for (int c = 0; c < n; ++c) { for (String left: generate(c)) { for (String right: generate(n - 1 - c)) { ans.add("(" + left + ")" + right); } } } } cache[n] = ans; return ans; } public List<String> generateParenthesis(int n) { return generate(n); } }