经典问题--php/go输出n对括号的所有组合

问题

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,则接下来出现的字符可能是‘(‘,也可能是‘)‘,可以:

  sappend字符‘(’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

经典问题--php/go输出n对括号的所有组合

 

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

经典问题--php/go输出n对括号的所有组合

 这里只是我自己根据解题思路所写的例子,如果大家有更好的方法,共同学习,共同进步。

 

经典问题--php/go输出n对括号的所有组合

上一篇:上传图片时遇到的错误(Invalid prop: type check failed for prop "image". Expected String, got Undefined.)


下一篇:CSS基础——5、css属性书写顺序