题目描述
要求生成所有“合法”的括号字符串，就首先需要弄清楚括号字符串的合法性定义，也就是说如果我们现在有一个由小括号组成的字符串，该如何判断其是否符合要求。此前做过判断括号串是否合法的题目，那道题目中一般在遍历过程中维护一个栈，因为每个后括号都需要在已经遍历的子串中找到自己对应的前括号。这个题目中的合法性判断应该稍微简单一些，因为本题中只有小括号一种括号，因此我们可以将使用栈存储前面遍历的元素，简化为使用一个整型变量维护前括号的数量。这样一来，实际实现过程可以使用open存储前括号的数量，close存储后括号的数量，遍历结束时只有open == close时字符串才合法，此外，整个遍历过程中open >= close都需要成立，毕竟后括号必须有且仅有一个对应的前括号。
bool check(string& s, int n) {int open = 0, close = 0;for (char c : s) {switch (c) {case '(':open++; break;case ')':close++; break;default:return false;}if (open > n) return false;if (close > open) return false;}return true;}
只关心open和close的大小关系，就可以将两个变量简化为一个变量balance，可以理解成前后括号的数量是否平衡。
bool check(string& temp) {int balance = 0;for (const char& c : temp) {if (c == '(') balance++;else balance--;if (balance < 0) return false;}if (balance == 0) return true;else return false;}
明确了如何判断括号字符串的合法性，就可以想用回溯算法枚举所有可能的括号字符串，将所有合法的结果存入结果数组中返回。
void backtrack(vector<string>& result, string& s, int idx, int n) {if (idx >= 2 * n) {if (check(s, n)) result.push_back(s);return;}s.push_back('(');backtrack(result, s, idx + 1, n);s.pop_back();s.push_back(')');backtrack(result, s, idx + 1, n);s.pop_back();}vector<string> generateParenthesis(int n) {vector<string> result;string s;backtrack(result, s, 0, n);return result;}
但是其实没有必要将整个串枚举完，而是可以在枚举过程中判断当前子串的合法性，即前括号与后括号的数量关系，因为显然如果前面一部分子串已经不合法，再继续深入下去的整个串一定不可能合法。这实际上也是一种对回溯算法的剪枝。
class Solution {
public:void backtrack(vector<string>& res, string& temp, int open, int close, int n) {if (temp.length() == n * 2) {res.push_back(temp);return;}if (open < n) {temp.push_back('(');backtrack(res, temp, open + 1, close, n);temp.pop_back();}if (close < open) {temp.push_back(')');backtrack(res, temp, open, close + 1, n);temp.pop_back();}}vector<string> generateParenthesis(int n) {vector<string> res;string temp;backtrack(res, temp, 0, 0, n);return res;}
};
顺带一提，这个题目需要对字符串进行回溯，C++中的字符串实际上就是一个字符向量数组，但是Java中需要使用StringBuilder或者StringBuffer提供的接口。根据力扣的提测结果，前者更快些（但是缺点在于线程不安全）。
