22括号生成

旧城等待， 2023-03-01 12:21 8阅读 0赞

## 一、前言 ##

标签：回溯算法。

问题来源LeetCode 22 难度：中等。

问题链接：[https://leetcode-cn.com/problems/generate-parentheses/][https_leetcode-cn.com_problems_generate-parentheses]

## 二、题目 ##

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

**示例：**

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

## 三、思路 ##

回溯法解决，可参考《[46全排序][46]》

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 022_GenerateParenthesis.h
    * @label   : 回溯算法
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107573657
    * @author  : niebingyu
    * @date    : 2020/07/25
    * @title   : 22.括号生成
    * @purpose : 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
    *
    * 示例：
    * 输入：n = 3
    * 输出：[
    *        "((()))",
    *        "(()())",
    *        "(())()",
    *        "()(())",
    *        "()()()"
    *      ]
    *
    *
    * 来源：力扣（LeetCode）
    * 难度：中等
    * 链接：https://leetcode-cn.com/problems/generate-parentheses/
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <unordered_map>
    #include <algorithm>
    #include <assert.h>
    using namespace std;
    
    #define NAMESPACE_GENERATEPARENTHESIS namespace NAME_GENERATEPARENTHESIS {
    #define NAMESPACE_GENERATEPARENTHESISEND }
    NAMESPACE_GENERATEPARENTHESIS
    
    class Solution
    {
    public:
        vector<string> generateParenthesis(int n)
        {
            vector<string> result;
            string current;
            backtrack(result, current, 0, 0, n);
            return result;
        }
    
    private:
        void backtrack(vector<string>& ans, string& cur, int open, int close, int n)
        {
            if (cur.size() == n * 2)
            {
                ans.push_back(cur);
                return;
            }
    
            if (open < n)
            {
                cur.push_back('(');
                backtrack(ans, cur, open + 1, close, n);
                cur.pop_back();
            }
    
            if (close < open)
            {
                cur.push_back(')');
                backtrack(ans, cur, open, close + 1, n);
                cur.pop_back();
            }
        }
    };
    
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, int n, vector<string> expect)
    {
        Solution s;
        vector<string> result = s.generateParenthesis(n);
    
        if (result == expect)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. " << endl;
    }
    
    // 测试用例
    void Test1()
    {
        int n = 3;
        vector<string> expect =
        {
            "((()))",
            "(()())",
            "(())()",
            "()(())",
            "()()()"
        };
    
        test("Test1()", n, expect);
    }
    
    NAMESPACE_GENERATEPARENTHESISEND
    // 测试 用例 END
    //
    void GenerateParenthesis_Test()
    {
        cout << "------ start 22.括号生成 ------" << endl;
        NAME_GENERATEPARENTHESIS::Test1();
        cout << "------ end 22.括号生成 --------" << endl;
    }

**执行结果：**

![20200725085831109.png][]

[https_leetcode-cn.com_problems_generate-parentheses]: https://leetcode-cn.com/problems/generate-parentheses/
[46]: https://blog.csdn.net/nie2314550441/article/details/107525867
[20200725085831109.png]: /images/20230208/f83ad1fb9f8145019d53be947419fb71.png