/*
 * @lc app=leetcode.cn id=22 lang=cpp
 *
 * [22] 括号生成
 */

// @lc code=start
class Solution {
    
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string track;
        if (n == 0) return res;
        backtrack(n, n, track, res);
        return res;
    }

    void backtrack(int left, int right, string& track, vector<string>& res) {
        if (left > right) return;
        if (left < 0 || right < 0) return;
        if (left == 0 && right == 0) {
            res.emplace_back(track);
            return;
        }

        track.push_back('(');
        backtrack(left - 1, right, track, res);
        track.pop_back();

        track.push_back(')');
        backtrack(left, right - 1, track, res);
        track.pop_back();
    }
};
// @lc code=end