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

2019-8-2 星期五 开始吧

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

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

题目描述

求所有加起来等于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);
                }
            }
        }
        
    }