题解 | #牛圈围栏问题#

考察知识点：回溯

题目分析：

题目想要我们用n个左括号和右括号组成一个左括号和右括号相匹配的字符串。即每个右括号匹配一个左括号，每个括号对都是左括号在左边，右括号在右边。同时结果是按照左括号较多的靠前的顺序输出。

因为第一个字符一定是左括号，我们可以以此为起点进行递归。首先每次都先尝试将左括号放入，之后尝试将右括号放入。左括号的放入条件就是字符串中左括号的个数不能大于n，有括号的放入条件是字符串中有括号的个数不能大于n，并且还不能大于左括号的个数。

注意回溯时应该恢复现场。

所用编程语言：C++

#include <ios>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    void dfs(vector<string> &result, string &s, int &leftNum, int &rightNum, int &cnt) {
        if (!leftNum && !rightNum) {
            result.push_back(s);
            return;
        }
        if (leftNum > 0) {
            leftNum--;
            s += "(";
            cnt++;
            dfs(result, s, leftNum, rightNum, cnt);
            s.pop_back();
            cnt--;
            leftNum++;
        }
        if (rightNum > 0 && cnt > 0) {
            rightNum--;
            s += ")";
            cnt--;
            dfs(result, s, leftNum, rightNum, cnt);
            s.pop_back();
            rightNum++;
            cnt++;
        }
    }
    vector<string> generateParenthesis(int n) {
        // write code here
        vector<string> result;
        int leftNum = n, rightNum = n;
        leftNum--;
        string s = "(";
        int cnt = 1;

        dfs(result, s, leftNum, rightNum, cnt);
        return result;
    }
};