题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

示例 2：

输入：n = 1
输出：[“()”]

提示：

1 <= n <= 8

题解

填入第1个空位后，需要考虑第2个空位需要填什么，
填入第2个空位后，需要考虑第3个空位需要填什么，
填入第3个空位后，需要考虑第4个空位需要填什么，
…

我们发现，存在相似性的子问题，那么使用递归可以解决。 在 2n 个格子填满的时候，递归终止。也就是上图中，在树的第 n 层递归终止。

class Solution {
public:
    vector<string> result;
    vector<string> generateParenthesis(int n) {
        doing(n, n, 2 * n, "");
        return result;
    }
    void doing(int left , int right , int leave , string str) {
        if (leave == 0) {
            result.push_back(str);
            return;
        }
        if (left > 0) {
            doing(left - 1, right, leave - 1, str + "(");
        }
        if (right > left) {
            doing(left, right - 1, leave - 1, str + ")");
        }
    }
};