Leetcode 22.括号生成【C++】

地址：https://leetcode-cn.com/problems/generate-parentheses/

题目

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

示例：

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

解题思路

首先感谢 labuladong 上面的两篇文章，这个题完全是靠这两篇文章学会的。

• labuladong 回溯算法详解：https://sohu.gg/i70eLLuTA
• labuladong 括号生成：https://sohu.gg/ZJ2b1P9tC

是的，我自己做了很久并没有做出来，然后看了 labuladong 这两篇关于回溯算法的文章，真的讲的很清晰明了，至少可以说是我所看过的所有文章里讲的把回溯讲的最清楚的了。万分感激，同时也强烈推荐 labuladong 的微信公众号，有很多很有用的原创文章。

这里我就不细说本题的解题思路了，附上 labuladong 的回溯算法框架：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

代码

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> vec;
        string str;
        backtrack(vec, str, n, n);
        return vec;
    }

    void backtrack(vector<string>& vec, string str, int left, int right) {
        if (left < 0 || right<0 || left>right)
            return;
        if (left == 0 && right == 0) {
            vec.push_back(str);
            return;
        }
        //放置左括号
        str += '(';//做选择
        backtrack(vec, str, left - 1, right);
        str.pop_back();//撤销选择

        //放置右括号
        str += ')';
        backtrack(vec, str, left, right - 1);
        str.pop_back();
    }
};