题目描述

22. Generate Parentheses 

回溯法

class Solution {vector<string> res;string cur;
public:vector<string> generateParenthesis(int n) {backtrack(n,0,0);return res;}void backtrack(int n,int left_count,int right_count){if(cur.size() == 2*n){//如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。//按照上述原则放括号，得到的括号序列就是合法的res.push_back(cur);return;}if(left_count<n){//如果左括号的数量小于n，可以放一个左括号cur+='(';backtrack(n,left_count+1,right_count);cur.pop_back();}if(right_count< left_count){//如果右括号的数量小于左括号的数量，可以放一个右括号cur+=')';backtrack(n,left_count,right_count+1);cur.pop_back();}}
};