括号(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+')');}}
};
更多推荐
[回溯法]面试题 08.09. 括号(medium)
发布评论