0022. 括号生成

[utterances-bot]

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

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]

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

[xiaos2021]

显式回溯

class Solution {
private:
    vector<string> res;
    string path;
    int limit;

    void backtrack(int open, int close) {
        if (path.size() == 2 * limit) {
            res.emplace_back(path);
            return;
        }

        if (open < limit) {
            path += '(';
            backtrack(open + 1, close);
            path.pop_back();
        }
        if (close < open) {
            path += ')';
            backtrack(open, close + 1);
            path.pop_back();
        }
        return;
    }

public: 
    vector<string> generateParenthesis(int n) {
        res.clear();
        path.clear();
        this->limit = n;
        backtrack(0, 0);
        return res;
    }
};

隐式回溯

class Solution {
private:
    vector<string> res;
    int limit;

    void backtrack(string cur, int open, int close) {
        if (cur.size() == 2 * limit) {
            res.emplace_back(cur);
            return;
        }

        if (open < limit) {
            backtrack(cur + '(', open + 1, close);
        }
        if (close < open) {
            backtrack(cur + ')', open, close + 1);
        }
        return;
    }

public: 

    vector<string> generateParenthesis(int n) {
        res.clear();
        this->limit = n;
        backtrack("", 0, 0);
        return res;
    }
};