[LeetCode 22] 括号生成

22. 括号生成

dfs+剪枝

本题使用dfs搜索，选(或者)两个分支。
观察出剪枝条件：不管进行到哪一位，(的数量都是>=)的，而且数量都不能超过n

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
 
class Solution {
  public:
    void dfs(int i, int n, int left, int right, vector<string> &res,
             string str) {
        //剪枝条件
        if (left < right || left > n)
            return;
        if (i >= 2 * n) {
            res.push_back(str);
            return;
        }

        str += '(';
        dfs(i + 1, n, left + 1, right, res, str);
        str[str.length() - 1] = ')';
        dfs(i + 1, n, left, right + 1, res, str);
    }
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string str;
        int left = 0, right = 0;
        dfs(0, n, left, right, res, str);
        return res;
    }
};

int main() {
    Solution s;
    vector<string> res;
    res = s.generateParenthesis(3);
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << endl;
    }

    cout << endl << res.size();

    return 0;
}