Leetcode基础刷题之PHP解析(216. Combination Sum III)

2019-8-2 星期五 开始吧


杭州找个人爬山这么难???

上一题链接Leetcode基础刷题之PHP解析(59. Spiral Matrix II)

979ccc0248ad7fa31a4fdf4e04ac9bec.png


题目描述


求所有加起来等于n并且元素个数为k的所有组合,值得注意的是每一个组合中1到9的数只能出现一次。


题目分析


需要遍历所有的情况,每一次组合过程中向数组添加一个元素x,就意味剩下要添加的元素个数为k-1,剩下目标数就是n-x,那么一个符合条件的一组数据就是同时满足$k==0 $n==0的时候,再举个列子,比如说当前这组数据已经有了[1,2],因为从1-9没有重复的值,下一个是3,发现和并不等于9,那么这时候就需要把3从当前组合中踢出去,下标向右移,来到4这个位置......一直到6这个位置的时候,$n=0,$k=0,符合,这就是其中一组正解。


代码实现

 /**
     * @param Integer $k
     * @param Integer $n
     * @return Integer[][]
     */
    function combinationSum3($k, $n) {
        $res=[];
        $list=[];
        
        $num=[1,2,3,4,5,6,7,8,9];
        $this->helper($res,$list,$num,$k,$n,0);
        return $res;
    }
    
    function helper(&$res,$list,$num,$k,$n,$start){
        if($k==0 && $n==0){
            array_push($res,$list);
        }else{
            for($i=$start;$i<count($num);$i++){
                if($k>0 && $n>0){
                    array_push($list,$num[$i]);
                    $this->helper($res,$list,$num,$k-1,$n-$num[$i],$i+1);
                    array_pop($list);
                }
            }
        }
        
    }

    这样的话就相当于递归了所有的情况,随便举个例子,k=3,n=5,拿其中一个场景,比如[1,4],第三个数从5开始已经没有计算的必要了,而且你会发现每一个整轮比较结束以后,下一轮不必要比较的数就$i+1,还是可以改进的。

吴亲库里 has written 98 articles

情绪只是对自己无能的愤怒

积分:4787 等级:P8 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?