使用 oh-my-zsh

22、括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

提示：

• $1 <= n <= 8$

思路 1

• 都知道两个极端情况：全嵌套和全部嵌套
• 递归最小问题：递归添加左右括号，保证做括号数量大于等于右括号数量

class Solution {
    
    // 规定一个嵌套的层级，递归实现,回溯
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        backtrack(ans,"",0,0,n);
        return ans;
    }
    // open 左括号的个数，close 右括号的个数
    public void backtrack(List<String> ans,String str,int open, int close,int max) {
        if (str.length() == (max*2)) {
            ans.add(str);
            return;
        }
        
        if (open < max) {// 递归在增加一个左括号 "("
            backtrack(ans,str+"(",open+1,close,max);
        }
        if (close < open){// 递归增加一个右括号 "("
            backtrack(ans,str+")",open,close+1,max);
        }
    }
}

// 基于StringBuilder来
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        generateParenthesis(n, 0, 0, new StringBuilder(), ans);
        return ans;
    }

    public void generateParenthesis(int n, int left, int right, StringBuilder string, List<String> list) {
        if (n * 2 == left + right) {
            list.add(string.toString());
        }

        // 先递归左括号
        if (left < n && left + right + 1 < 2 * n) {
            generateParenthesis(n, left + 1, right, string.append("("), list);
            string.deleteCharAt(string.length() - 1);
        }
        // 再递归右括号
        if (left > 0 && right < left) {
            generateParenthesis(n, left, right + 1, string.append(")"), list);
            string.deleteCharAt(string.length() - 1);
        }
    }
}

思路 2 动态规划思想

• 局部最优解一定是全局最优解的一部分
• 所以逐渐增加括号的总数量，逐渐构造全局最优解

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        if (n == 0) {// 终止递归
            ans.add("");
        } else {// 递归构造解集合
            for (int c = 0; c < n; ++c)// n组括号
                for (String left: generateParenthesis(c))// 局部解c组括号
                    for (String right: generateParenthesis(n-1-c))// 局部解n-c-1组括号
                        // left+right == n-1 因为这里多了一组 ()
                        ans.add("(" + left + ")" + right);
        }
        return ans;
    }
}

// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/two-sum/solution/gua-hao-sheng-cheng-by-leetcode/

C++ 版 纯动态规划代码 递归求解其实是棵树，深度优先构造即可

class Solution{
public:
    vector<string> ans;int N;
    void dfs(int l,int r,string has){
        if(r > l) return;       // 右括号的数量不能大于左括号的数量
        if(l > N) return;       // 左括号的数量不能大于括号总数
        if(l == r && r == N){   // 递归正常，此时所有括号添加完毕
            ans.push_back(has);return;// 加入一个局部解到解集中，返回
        }
        dfs(l+1,r,has + "(");   // 递归添加左括号
        dfs(l,r+1,has + ")");   // 递归添加右括号
    }
    vector<string> generateParenthesis(int n) {
        N=n;if(!N) return {};
        dfs(0,0,"");// 深度优先搜索
        return ans;
    }

// 作者：sanxiconze-2
// 链接：https://leetcode-cn.com/problems/two-sum/solution/cban-ben-bao-li-gou-zao-fa-jian-zhi-by-sanxiconze-/
};

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com