问题
n对括号有多少种合法的组合，写出一个可以执行出该结果的函数：
当n=1时,输出["()"];
当n=2时,输出["(())","()()"];
当n=3时,输出["((()))","(()())","(())()","()(())","()()()"];
思路
问题等价为：在一个字符串中包含两种字符：‘(‘和‘)‘，他们出现的次数都为n，并且任何时候‘(‘出现的次数总是大于或等于‘)‘出现的次数。
解决方案：（递归）
标志：l: 左括号出现的次数，r:右括号出现的次数，n: 括号对数，s: 存储符合要求的排列字符串，num: 匹配排列种数,arr：存储结果集;
步骤：
1.如果r=n，即右括号已出现了n次，则num++，打印s，返回；
2.如果r=l，即左右括号出现次数相等（且<n，这由1知），则在s后面append字符‘(’，并l++，回到1（递归）；
3.如果r<l，即右括号出现次数小于左括号，分两种情况
（1），l=n，即左括号全部出现，则在s后面append字符‘)‘，并r++，回到1（递归）；
（2），l<n，则接下来出现的字符可能是‘(‘，也可能是‘)‘，可以：
在s后append字符‘(’，l++，回到1（递归）；然后把s最后的字符‘(‘pop出来，append字符‘)’，l--,r++,再回到1（递归）；
解题思路参考链接：
https://blog.csdn.net/u014529413/article/details/39119273
知道了解题思路，那么现在就可以用语言程序来编写测试输出结果：
1.用php实现：
代码示例(这里我用了php7的写法):
<?php // 严格模式 declare(strict_types=1); /** * 输出n对括号组合 * @param int $l [l表示已有左括号个数] * @param int $r [r表示已有右括号个数] * @param int $n [n表示括号对数] * @param string $s [存储符合要求的排列字符串] * @param int &$num [引用传递:匹配排列种数n] * @param array &$arr [引用传递:結果集] * @return array [description] */ function nBrackets(int $l,int $r,int $n,string $s,int &$num,array &$arr):array{ if($r == $n){ $num++; // echo "$s\n"; $arr[] = $s; return $arr; } if($r == $l) { $s=$s.‘(‘; $l++; nBrackets($l,$r,$n,$s,$num,$arr); }else{ //$r<$l if($l == $n){ $s=$s.‘)‘; $r++; nBrackets($l,$r,$n,$s,$num,$arr); }else{ $s=$s.‘(‘; $l++; nBrackets($l,$r,$n,$s,$num,$arr); $s = substr($s,0,strlen($s)-1); $l--; $s=$s.‘)‘; $r++; nBrackets($l,$r,$n,$s,$num,$arr); } } return $arr; } $n=4; $num=0; $s=‘‘; $arr = array(); $arrRs = nBrackets(0,0,$n,$s,$num,$arr); echo json_encode($arrRs,JSON_UNESCAPED_UNICODE); echo "\n共".$num."种";
输出结果：
["(((())))","((()()))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"]
共14种
2.用go实现：
代码示例(go的类型声明是放在变量后面，与其他语言有些区别)：
package main import "fmt" /** * 输出n对括号组合 * @param l int [l表示已有左括号个数] * @param r int [r表示已有右括号个数] * @param n int [n表示括号对数] * @param s string [存储符合要求的排列字符串] * @param $num int [引用传递:匹配排列种数n] * @param $arr array [引用传递:結果集] * @return array [description] */ func nBrackets(l int,r int,n int,s string,num *int,arr *[]string) []string { if(r == n){ *num ++ //println(s,"\n") *arr = append(*arr,s) return *arr } if(r == l) { s = fmt.Sprintf("%s%s", s, "(") l++ nBrackets(l,r,n,s,num,arr) }else{ //r<l if(l == n){ s = fmt.Sprintf("%s%s", s, ")") r++ nBrackets(l,r,n,s,num,arr) }else{ s = fmt.Sprintf("%s%s", s, "(") l++ nBrackets(l,r,n,s,num,arr) s = s[:len(s)-1] l-- s = fmt.Sprintf("%s%s", s, ")") r++; nBrackets(l,r,n,s,num,arr) } } return *arr } func main() { var n int =4 var num int =0 var s string ="" var arr []string var arrRs []string arrRs = nBrackets(0,0,n,s,&num,&arr) fmt.Println(arrRs) fmt.Print("共",num,"种") }
输出结果：
[(((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()()]
共14种
这里只是我自己根据解题思路所写的例子，如果大家有更好的方法，共同学习，共同进步。