0022. 括号生成

[utterances-bot]

0022. 括号生成 | 算法通关手册

22. 括号生成 # 标签：字符串、回溯算法 难度：中等 题目大意 # 给定一个整数 n，生成所有有可能且有效的括号组合。 解题思路 # 通过回溯算法生成所有答案。为

https://algo.itcharge.cn/Solutions/0001-0099/generate-parentheses/

[S1mpleBug]

附上C++代码

class Solution {
public:
    vector<string> res;
    string tmp;
    void dfs(int &n, int symbol, int idx) {
        if(2*n == idx) {
            if(symbol == 0)
                res.push_back(tmp);
            return;
        }

        if(symbol < n) {
            tmp.push_back('(');
            dfs(n, symbol+1, idx+1);
            tmp.pop_back();
        }

        if(symbol > 0) {
            tmp.push_back(')');
            dfs(n, symbol-1, idx+1);
            tmp.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0);
        return res;
    }
};

[yanbigong2]

有没有机会在生成步骤就判断括号是否合理剪枝呀？