22-括号生成

LeetCode 22. Generate Parentheses

LeetCode-22

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

method

递归参数：左括号和右括号数量，当前节点值，递归深度n

因为需要比较左括号和右括号的数量，所以就把左括号和右括号的数量放到递归参数里，path放在参数里，回溯的代码简洁一点

递归结束条件：当前节点长度为2*n

单层遍历逻辑：如果有左括号可以用，就用左括号；如果右括号的数量小于左括号，就可以用右括号

vector<string> res;
void dfs(int left, int right, string path, int n) {
    if (path.size() == 2 * n) {
        res.push_back(path);
        return;
    }
    if (left < n) {
        dfs(left + 1, right, path + "(", n);
    }
    if (left > right) {
        dfs(left, right + 1, path + ")", n);
    }
}
vector<string> generateParenthesis(int n) {
    dfs(0, 0, "", n);
    return res;
}