[回溯法]面试题 08.09. 括号(medium)

括号(medium)"/>

[回溯法]面试题 08.09. 括号(medium)

题目：

题解：

• 回溯法经典题型
• 题目中的 n 表示括号的个数，那么我们用 n 来表示左括号的个数'('，那么每使用一个左括号，同时产生一个可使用的右括号数')'，可以保证不会产生无效括号。
• 可行解的生成：可使用的左右括号数都为0时，表示生成一个有效的括号。

代码如下：

class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> res;backtrack(res,n,0,"");return res;}//回溯：left表示可使用的做左括号数'(',right表示可使用的右括号数')'void backtrack(vector<string>& res,int left,int right,string track){if(!right&&!left)res.push_back(track);else{/*使用一个左括号，同时可使用右括号数加1，这样可避免生成无效括号*/if(left>0)backtrack(res,left-1,right+1,track+'(');/*可使用的右括号数大于0，则用来补齐原来的左括号*/if(right>0)backtrack(res,left,right-1,track+')');}}
};