(递归+回溯)leetcode中等22. 括号生成

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

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

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

提示：
1 <= n <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解读题意，给定一个数字n，要求返回一个字符串数组，并且其中每个字符串都是长度为2*n且每个字符都为‘（’或者‘）’的合法序列
例如n=1时，“()”是和符合题意的，“)(”是不符合题意的。
字符的种类只有两种，且字符串的长度是固定的，所以这里我们可以使用递归，分别当作是两种情况，一种情况是选择要左括号，另一种是选择要右括号。
大致的思路就是，先从一种情况深入，然后回溯，再从另一种情况深入

初始化主要以递归需要的变量以及我们需要的答案为主，一个是现在传递的数组，代表当前一个字符串的情况，第二是储存答案的数组

		vector nowarr;
		vector > ans;

递归的参数
1.当前储存字符的数组
2.存放字符串的答案
3.字符串长度的限制
4.当前字符串的长度

递归经典的两个步骤1.出口2.现在能做的事情
首先判断现在能做的事情
将左括号加入到当前的字符数组中，然后进行深入的递归1，回溯，将当前的字符删除，然后将右括号加入到字符数组中，然后进行递归深入2

		//现在做的事情
		nowarr.push_back('(') ;
		recursion_back(nowarr,ans,n,i+1);
		nowarr.pop_back();			//回溯 
		nowarr.push_back(')');
		recursion_back(nowarr,ans,n,i+1);

出口
判断当前的字符串长度是否等于字符串长度的最大限制，如果相等再进行判断，当前的字符串是否合法(需要新写一个函数)，如果合法，将当前的字符串加入到答案的数组中，最后返回

		//出口
		if(i>=n)
		{
			if(isok(nowarr))
				ans.push_back(nowarr);
			return ;
		}

首先分析括号是如何匹配的，原理是通过栈，如果遇到左括号就压入栈中，如果遇到了右括号就就将当前的栈顶元素pop，如果遇到了右括号，但是当前栈为空，说明没有左括号可以与之匹配，直接返回false，判断结束后，还需要判断当前的栈是否为空，如果不为空，说明栈中的左括号没有与之匹配的右括号

	bool isok(vector nowarr)		//判断当前序列是否合法 
	{
		stack str;
		for(int i=0;i 
完整代码 
class Solution {
public: 
	bool isok(vector nowarr)		//判断当前序列是否合法 
	{
		stack str;
		for(int i=0;i nowarr,vector > &ans,
	int n,int i)
	{
		//出口
		if(i>=n)
		{
			if(isok(nowarr))
				ans.push_back(nowarr);
			return ;
		}
		//现在做的事情
		nowarr.push_back('(') ;
		recursion_back(nowarr,ans,n,i+1);
		nowarr.pop_back();			//回溯 
		nowarr.push_back(')');
		recursion_back(nowarr,ans,n,i+1); 
	}
	
    vector generateParenthesis(int n) {
		vector nowarr;
		vector > ans;
		
		recursion_back(nowarr,ans,n*2,0);
		
		vector ans1;
        string str(n*2,'0');

		for(int i=0;i 
总结 
当有固定的情况时，比如可以选这种或者可以选那种，但是情况的数量是小规模的，而且内循环的次数我们不容易确定，这个时候我们可以选择递归+回溯，先选一种情况深入递归，然后回溯删除这种情况的选择，再选下一种情况进行深入递归
 递归的优点在于，有些时候思路很很好想，不如二叉树的深度优先搜索，或者再迷宫中找一种出口路径等等，缺点在于时间复杂度有些时候比较高，因为递归很容易造成重复的情况，或者是完全没必要的情况，这个时候我们也可以做优化，比如剪枝和记忆化搜索，剪枝就是排除掉一些没有必要的搜索，记忆化搜索是改递归有大量的重复搜索，这个时候我们可以记录每个递归的结果，当需要这个结果的时候，我们直接将结果从数组中拿出来，达到用空间换时间