怎么样才是合法的组合?
只要每一时刻保证左括号的数目>=右括号的数目即可。
直接递归就行,每次递归加一个括号,左括号只要还有就能加,右括号要保证加进去之后右括号总数不大于左括号总数
void insert_parentheses(char *res, int l, int r){
if(l==0&&r==0)
cout<<res;
else{
if(l>0){
res[n-l-r]='(';
insert_parenthese(res,l-1,r);
}
if(r>l){
res[n-l-r] = ')';
insert_parenthese(res,l,r-1);
}
} }
例如2的时候
(
(),((
()(,(()
()(),(())
只有两种合法组合
另外如果不是求组合而是求可能的方案的话解法是catalan数,可以参考下一篇文章: