剪枝算法（括号生成）

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

 

示例 1：

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

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

提示：

1 <= n <= 8

由题目可知，每个左括号都必须有对应的右括号​，寻找满足这一条件的所有的组合，由此，我们可以把该问题拆成两部分， 遍历与剪枝

1. 遍历

   n对括号，则生成的字符串共2n​个字符，n​个左括号，n​个右括号，我们先要讨论每个字符位取左括号的情况，讨论完毕后我们需要将该字符位替换为右括号继续讨论，很明显的递归调用特征，刚好满足调用不改变原变量的特征，我们可以用left​与right​两个变量来表示左右括号剩余可取数量，当任意一种括号全部放入后，剩下的字符位全部取另一种括号，当left​与right​均为0​时走到尽头，将本次结果存入输出output​数组，随后从递归中返回进行下一种讨论，由此我们可以实现所有可能性的遍历

2. 剪枝

   我们需要在遍历过程中筛选出不满足每个左括号都必须有对应的右括号​的树枝减去，仔细观察易知要满足这一条件，则任何时候左括号数量都应当大于等于右括号数量，所以我们淘汰所有right<left​的情况即可达到目的

3. 代码实现

   class Solution {
   public:
       vector<string> generateParenthesis(int n) {
           int left = n;
           int right = n;
           vector<string> output;
           this->runself(n, n, output, "");
           return output;
       }
   
       void runself(int left, int right, vector<string>& output, string now){
           if(left==0&&right==0){
               output.push_back(now);
               return;
           }
           if(left>0){
               runself(left-1,right,output,now+'(');
           }
           if(right>0&&left<right){
               runself(left,right-1,output,now+')');
           }
           return;
       }
   
   };
   

‍