本文最后更新于:2020年4月9日 晚上

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

题目

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

示例:

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

解题思路

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

是的,我自己做了很久并没有做出来,然后看了 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();
    }
};