leetcode 链接：22. 括号生成

题目

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

示例：

  1. 输入：n = 3
  2. 输出：["((()))","(()())","(())()","()(())","()()()"]
输入：n = 1
输出：["()"]

解答 & 代码

递归回溯 

class Solution {
private:
    // 递归回溯
    // n：需要生成的括号总对数；left：当前已生成的左括号数；right：当前已生成的右括号数
    void backtrack(int n, int left, int right, string& result, vector<string>& resultList)
    {
        // 递归结束条件
        if(result.size() == 2 * n)
        {
            resultList.push_back(result);
            return;
        }

        if(left < n)    // 如果当前已生成的左括号数<n
        {
            result += "(";        // 生成左括号
            backtrack(n, left + 1, right, result, resultList);
            result.pop_back();    // 回溯
        }
        if(right < left)    // 如果当前已生成的右括号数<已生产的左括号数
        {
            result += ")";        // 生成右括号
            backtrack(n, left, right + 1, result, resultList);
            result.pop_back();    // 回溯
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        string result;
        vector<string> resultList;
        backtrack(n, 0, 0, result, resultList);
        return resultList;
    }
};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：11.2 MB, 在所有 C++ 提交中击败了 66.50% 的用户