【PHP】从数列1，2，3.......n 中随意取几个数,使其和等于m(一段神奇的代码)

￡神魔★判官ぃ 2022-06-08 00:42 140阅读 0赞

链接：[https://www.nowcoder.com/questionTerminal/11cc498832db489786f8a03c3b67d02c][https_www.nowcoder.com_questionTerminal_11cc498832db489786f8a03c3b67d02c]  
来源：牛客网

输入两个整数 n 和 m，从数列1，2，3…….n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来  
输入描述:

每个测试输入包含2个整数,n和m

输出描述:

按每个组合的字典序排列输出,每行输出一种组合

示例1  
输入

5 5

输出

1 4  
2 3  
5

没有任何思路，无奈。。。。。。

看到一大神代码，精彩至极，我给改造成了PHP,贴出来，供以后慢慢品尝。

<?php 
    $str = trim(fgets(STDIN));
    $n = explode(" ", $str)[0];
    
    $m = explode(" ", $str)[1];
    
    function help($n, $m, $arr, $beg){
            //echo "{
        $n}---{
        $m}---".count($arr)."---{
        $beg}".PHP_EOL;
            //var_dump($arr);
            //echo PHP_EOL;
            if($m == 0){//如果最后加起来有等于m的，则输出栈里面的所有内容，否则什么都不做，直接出栈
                    for($i=0; $i<count($arr); $i++){
                            //$i==0?(echo $arr[$i]):(echo " ".$arr[$i]);
                            if($i==0){
                                    echo $arr[$i];
                            }else{
                                    echo " ".$arr[$i];
                            }   
                    }   
                    echo PHP_EOL;
            }   
    
            for($j = $beg; $j<=$n&&$j<=$m; $j++){
                    array_push($arr, $j);//入栈
                    help($n, $m-$j, $arr, $j+1);
                    array_pop($arr);//出栈
            }   
    }
    
    $arr = []; 
    help($n, $m, $arr, 1);

测试：

[root@VM_114_93_centos exam]# php renyinqiuhe.php 
    5 6
    1 2 3
    1 5
    2 4
    [root@VM_114_93_centos exam]# php renyinqiuhe.php 
    9 9
    1 2 6
    1 3 5
    1 8
    2 3 4
    2 7
    3 6
    4 5
    9

[https_www.nowcoder.com_questionTerminal_11cc498832db489786f8a03c3b67d02c]: https://www.nowcoder.com/questionTerminal/11cc498832db489786f8a03c3b67d02c