力扣22. 括号生成

回溯

• 思路：
  • 定义函数 dfs(item, open, close, n) 表示当前 item 有左括号个数 open 和右括号个数 close ；
  • 使用递归，长度为 n 的序列就是在长度为 n - 1 的序列后加左括号或者右括号：
    • 先放左括号，只要其个数 < n；
    • 然后放右括号，只要右括号个数比左括号个数少；
    • 当 item = 2 * n 时（左括号 n + 右括号 n）item 构建完成，保存进结果；

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        std::string item;
        dfs(item, 0, 0, n);

        return result;
    }

private:
    void dfs(std::string& item, int open, int close, int n) {
        if (item.size() == 2 * n) {
            result.push_back(item);
            return;
        }
        if (open < n) {
            item.push_back('(');
            dfs(item, open + 1, close, n);
            item.pop_back();
        }
        if (close < open) {
            item.push_back(')');
            dfs(item, open, close + 1, n);
            item.pop_back();
        }
    }

private:
    std::vector<std::string> result;
};

——————————————————————————————————————————