【LeetCode】22.括号生成

• 问题描述
• 法I：回溯

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

有效括号组合需满足：左括号必须以正确的顺序闭合。

示例 1：

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

示例 2：

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

提示：
1 <= n <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

来看看代码吧：

//括号生成
//回溯法（递归）
class Solution {
public:
	vector generateParenthesis(int n) {//n为括号的对数
		vector re;//存结果：所有可能的字符串
		string singleRe;//存单个字符串
		stack st;
		int max = 0;//记录已经入栈的最多的左括号个数
		backtrack(0, n, re, singleRe, st, max);
		return re;
	}
	void backtrack(int dimension, int n, vector &re, string &singleRe, stack &st, int &max) {
		if (dimension == 2 * n) {
			re.push_back(singleRe);
			return;
		}
		else {
			for (int i = 0; i < 2; i++) {//列举该结点所有可能的子结点
				if (i == 0) {//左括号
					if (max < n) {
						st.push('(');
						singleRe += '(';
						max++;
						backtrack(dimension + 1, n, re, singleRe, st, max);
						st.pop();
						singleRe = singleRe.substr(0, singleRe.size() - 1);
						max--;
					}
					else {//剪枝
						;
					}
				}
				else {//右括号
					if (st.size() != 0) {
						st.pop();
						singleRe += ')';
						backtrack(dimension + 1, n, re, singleRe, st, max);
						st.push('(');
						singleRe = singleRe.substr(0, singleRe.size() - 1);
					}
					else {//剪枝
						;
					}
				}
			}
			return;
		}
	}
};

看看执行结果：

提几个踩坑点吧（其实我觉得刷题就是不断遇到踩坑点，然后下次就不会再踩了）：

1. 一定要注意到所有剪枝的可能情况啊！！！这道题里面有两种情况：一个是遇到右括号时发现栈里面为空，另外一个是左括号多于n了（这个情况我一开始就忘了555）
2. 剪枝其实也就是不再考虑这个子结点的所有子结点了，因此也就不会到达最终的叶子结点并加入结果集中，我们可以直接不用管它（千万不要在这里直接return啊，因为这个仅仅是当前状态的子结点，还有其他子结点没有遍历完成呢）。如果要剪枝的话，需要在这个结点（当前状态）的所有子结点遍历完成之后再return。

回溯有关return还是要好好想想！！！！（后面再想吧今天想不下去了）
应该是：到达最终的叶子节点和剪枝时需要return。