题目
给出? n? 代表生成括号的对数, 请你写出一个函数, 使其能够生成所有可能的并且有效的括号组合.
例如, 给出? n = 3, 生成结果为:
- [
- "((()))",
- "(()())",
- "(())()",
- "()(())",
- "()()()"]
链接:
题解
方法一 回溯
回溯法使用递归, 并在递归过程中考虑剪枝. 此外, 递归要考虑终止条件, 考虑传的参数, 参数可以包括结果的集合, 一直要用的变的量, 随着递归层数不同变化的计数量, 临时的作为最终结果的 str.
此题目中, 从长度为 0 到长度为 2n 递归生成一组有效括号组合, 满足条件的下一层递归分支才进入 (即进行了剪枝): 当当前左括号数量 < n 时, 可以加一个左括号; 当当前右括号数量小于左括号数量时, 可以加一个右括号. 这样保证所有生成的括号都是有效的.
方法二 DP
大概递归思想:
dp[n]='('+dp[i]+')'+dp[n-1-i] ,n 从 0 到用户输入的 N, 对于计算 dp[n] 遍历所有可能的 i,
, 其中 dp[n] 表示长度为 2*n 的所有有效串.
存储方法也很有意思, 用 List<List> ans, 最终用 ans.get(n) 获得长度为 2*n 的所有有效括号组合.
方法一二的时间复杂度相同, 都只遍历了有效的分支, 且没有重复.?
代码
代码一 回溯
- class Solution {
- public static List<String> generateParenthesis(int n) {
- List<String> parenthesis = new ArrayList<>();
- traceBack("", 0, 0, n, parenthesis);
- return parenthesis;
- }
- private static void traceBack(String str, int left, int right, int n,
- List<String> parenthesis) {
- if (str.length() == 2 * n) {
- parenthesis.add(new String(str));
- return;
- }
- if (left <n) {
- traceBack(str + '(', left + 1, right, n, parenthesis);
- }
- if (right < left) {
- traceBack(str + ')', left, right + 1, n, parenthesis);
- }
- }
- }
代码二 DP
- class Solution {
- public List<String> generateParenthesis(int n) {
- List<List<String>> parenthesis = new ArrayList<>();// 所有长度 <=2n 的括号组合
- // 将长度为 0 的括号组合, 放入 parenthesis
- ArrayList<String> list = new ArrayList<>();
- list.add("");
- parenthesis.add(list);
- // 由 nn 为 1 至 n 一层层算 2*nn 长度的括号组合, 放入 parenthesis
- for (int nn = 1; nn <= n; ++nn) {
- List<String> parenthesisTemp = new ArrayList<>();
- for (int leftLen = 0; leftLen <= nn - 1; ++leftLen) {
- for (String leftStr : parenthesis.get(leftLen)) {
- for (String rightStr : parenthesis.get(nn - 1 - leftLen)) {
- parenthesisTemp.add(new String('(' + leftStr + ')' + rightStr));
- }
- }
- }
- parenthesis.add(parenthesisTemp);
- }
- return parenthesis.get(n);
- }
- }
[LeetCode] 22. 括号生成 (回溯 / DP)
来源: http://www.bubuko.com/infodetail-3340304.html