经典问题--php/go输出n对括号的所有组合
2021-05-31 00:04
标签：解决方案 代码示例 输出 要求 info ict func encode 根据 n对括号有多少种合法的组合，写出一个可以执行出该结果的函数： 当n=1时,输出["()"]; 当n=2时,输出["(())","()()"]; 当n=3时,输出["((()))","(()())","(())()","()(())","()()()"]; 问题等价为：在一个字符串中包含两种字符：‘(‘和‘)‘，他们出现的次数都为n，并且任何时候‘(‘出现的次数总是大于或等于‘)‘出现的次数。 解决方案：（递归） 标志：l: 左括号出现的次数，r:右括号出现的次数，n: 括号对数，s: 存储符合要求的排列字符串，num: 匹配排列种数,arr：存储结果集; 步骤： 1.如果r=n，即右括号已出现了n次，则num++，打印s，返回； 2.如果r=l，即左右括号出现次数相等（且 3.如果r （1），l=n，即左括号全部出现，则在s后面append字符‘)‘，并r++，回到1（递归）； （2），l 在s后append字符‘(’，l++，回到1（递归）；然后把s最后的字符‘(‘pop出来，append字符‘)’，l--,r++,再回到1（递归）； 解题思路参考链接： https://blog.csdn.net/u014529413/article/details/39119273 知道了解题思路，那么现在就可以用语言程序来编写测试输出结果： 1.用php实现： 代码示例(这里我用了php7的写法): 输出结果： ["(((())))","((()()))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"] 共14种 2.用go实现： 代码示例(go的类型声明是放在变量后面，与其他语言有些区别)： 输出结果： [(((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()()] 共14种 这里只是我自己根据解题思路所写的例子，如果大家有更好的方法，共同学习，共同进步。 经典问题--php/go输出n对括号的所有组合 标签：解决方案 代码示例 输出 要求 info ict func encode 根据 原文地址：https://www.cnblogs.com/qingfj/p/14641337.html问题
思路
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
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."种";
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
