思路：
递归生成所有可能在，为了节约时间，从中加入balance，当balance为负数一定不合法，就不递归了
当缺少 ( 就加入 ( ，多了就不递归了
当缺少 ) 就加入 ) ，多了就不递归了
当且仅当 ( 和 ）的个数等于n ，且balance
# include<iostream> # include<vector> # include<string> # include<algorithm> # include<math.h> # include<climits> # include<stack> using namespace std; void generate(int& n, int &balance, int &left,int &right,string &pushstr,vector<string> &res) { if (balance < 0)return; if (left > n) return; if (right > n) return; if (left == n && right == n) { res.push_back(pushstr); return; } for (int i = 0; i < 2; i++) { if (!i) {//第一次 if (left < n ) { left++; pushstr += '(';//( 优先生成 balance++; generate(n, balance, left, right, pushstr, res); pushstr.pop_back();//将刚才的 ( 消掉 left--; balance--; } } else { if (right < n) { right++; pushstr += ')'; balance--; generate(n, balance, left, right, pushstr, res); pushstr.pop_back();//将刚才的 ( 消掉 right--; balance++; } } } } vector<string> generateParenthesis(int n) { vector<string> res; int left = 0,right=0; string pushstr = ""; int balance = 0; generate(n, balance, left,right,pushstr, res); for (int i = 0; i < res.size(); i++) cout << res[i] << endl; return res; } int main(void) { generateParenthesis(3); system("pause"); return 0; }
