1.题目介绍

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

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]

提示：
1 <= n <= 8

2.题解

2.1 暴力枚举

思路

我们利用递归枚举出n对括号（这里是n对，说明共有2n个括号）即共2^2n种情况，并在其中找到正确的括号匹配情况。
1.递归返回条件，一次次加入'('和')'后，最终字符串长度到达n之后，进行合法性检验，若正确，加入结果数组中
2.合法性检验，必须随时满足左边括号多于等于右边括号数量，最终两边括号数量必须相等。
3.递归过程，现将当前字符串加上'('，继续递归，后删除这个'(',再加上')'进行继续递归。
4.注意条件给的是n对，所以最开始填参数时，总数量应为2*n;

代码

class Solution {
private:
    bool vaild(string &curr){
        int balance = 0;
        for(char ch:curr){
            if (ch == '(') balance++;
            else balance--;
            if(balance < 0) return false;
        }
        return balance == 0;
    }
    void generateAll(vector<string> &ans, int n, string &current){
        if(n == current.size()){
            if(vaild(current)){
                ans.push_back(current);
            }   
            return;
        }
        current += '(';
        generateAll(ans,n,current);
        current.pop_back();
        current += ')';
        generateAll(ans,n,current);
        current.pop_back();
    }

public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string current;
        generateAll(ans, 2*n, current);
        return ans;
    }
};

复杂度分析

2.2 回溯法

思路

方法2.1有一个问题，就是当已经出现了不满足情况的括号组合，他依旧会继续递归下去，直到达到总括号数才会进行合法性检验，这样就浪费了很多递归资源
我们这里在每次递归中加入两个标记位置，分别标记已有的左括号数和有括号数目，左括号数目open < n(总共2n，左边的肯定要<n, =n的时候再加就超出了),有括号数目close < open < n即可。

这里所谓的回溯就是，在遇到不满足递归条件的中途节点，不会继续递归，而是回溯到上一级节点。这里就是使用if判断直接跳过本次递归过程，函数完成后自动回溯上一级调用节点。

代码

class Solution {
private:
    void backtrack(vector<string> &ans, int n, int open, int close, string &curr){
        if(n*2 == curr.size()){
            ans.push_back(curr);
            return;
        }
        if(open < n){
            curr += '(';
            backtrack(ans, n, open + 1, close, curr);
            curr.pop_back();
        }
        if(close < open){
            curr += ')';
            backtrack(ans, n, open, close + 1, curr);
            curr.pop_back();
        }
    }
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string curr;
        backtrack(ans, n, 0, 0, curr);
        return ans;
    }
};

复杂度分析