题解 | #牛圈围栏问题# 回溯

知识点

回溯

思路

题意其实是问你，一个括号对数为n的全部合法字符串。

可以二进制枚举或者回溯来解决，二进制枚举的时间复杂度是，回溯的复杂度是

因此考虑用回溯来做，考虑字符串的从左往右的每个位置填左括号还是右括号，由于答案要求左括号优先，我们先考虑左括号，后考虑右括号。

注意必须是合法字符串，任何时候左括号的数量不少于右括号。

AC Code（c++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> generateParenthesis(int n) {
        vector<string> res;

        function<void(string&, int, int)> dfs = [&](string& path, int l, int r) {
            if (l > r) return;
            if (l == 0 and r == 0) {
                res.push_back(path);
                return;
            }
            if (l > 0) {
                path.push_back('(');
                dfs(path, l - 1, r);
                path.pop_back();
            }
            if (r > 0) {
                path.push_back(')');
                dfs(path, l, r - 1);
                path.pop_back();
            }
        };
        string s;
        dfs(s, n, n);
        return res;
    }
};