LeetCode 22 括号生成

LeetCode 22 括号生成

https://leetcode.cn/problems/generate-parentheses/description/

我们控制两个量，一个是左括号的个数a，另一个是右括号应该有的个数b，每向字符串中添加一个左括号就应该让a减少1然后让b增加1，每向字符串中增加右括号就应该让b减少1，以此构造字符串。
每一步可有两个分支，一个是向字符串中增添左括号，另一个是增添右括号，然后就DFS。

class Solution {
public:
    vector<string> vec;
    void dfs(int a, int b, string str) {
        if (a == 0 && b == 0)
        {
            vec.push_back(str);
            return;
        }


        if (a != 0) {
            dfs(a-1,b+1,str + "(");
        }

        if (b != 0) {
            dfs(a,b-1,str + ")");
        }

    }

public:
    vector<string> generateParenthesis(int n)
    {
        int a = n;
        int b = 0;
        dfs(a,b,"");
        return vec;
    }
};