22. 括号生成

方法：度优先遍历
我们以 n = 2 为例，画树形结构图。方法是 “做减法”。

画图以后，可以分析出的结论：

1.当前左右括号都有大于 0 个可以使用的时候，才产生分支；

2.产生左分支的时候，只看当前是否还有左括号可以使用；

3.产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；

4.在左边和右边剩余的括号数都等于 0的时候结算。

class Solution {
    public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        dfs("", n, n, &result);
        return result;
    }
    /**
     * @param str 当前递归得到的结果
     * @param left   左括号还有几个可以使用
     * @param right  右括号还有几个可以使用
     * @param result    结果集
     */
    void dfs(std::string str, int left, int right, vector<string>* result) {
        if(result == nullptr) {
            return;
        }
        if(left == 0 && right == 0) {
            result->push_back(str);
        }
        // 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
        if(left > right) {
            return;
        }
        if(left > 0) {
            dfs(str+"(", left-1, right, result);
        }
        if(right > 0) {
            dfs(str+")", left, right-1, result);
        }
    }
};

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        std::string path;
        int left = 0;
        int right = 0;
        std::vector<std::string> result;
        dfs(n, left, right, result, path);
        return result;
    }
    void dfs(int n, int left, int right, std::vector<std::string>& result, std::string& path) {
        cout << path << std::endl;
        if (left == right && left == n) {
            result.push_back(path);
            return;
        }
        if (right > left) {
            return;
        }
        if (left <= n) {
            path.push_back('(');
            dfs(n, left+1, right, result, path);
            path.pop_back();
        }
        path.push_back(')');
        dfs(n, left, right+1, result, path);
        path.pop_back();
    }
};

题解：力扣