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


递归第二天

Leetcode基础刷题之PHP解析(17. Letter Combinations of a Phone Number)

0d80e46e38fcd11aa4243db9d731f7dd.png


给定一个数组和一个目标数,求所有加起来等于目标数的组合,注意一个数可以被多次利用,但是组合是唯一的,不能有重复的组合。


这里我定义了三个变量,用来记录当前递归的数组下标,每次产生一个结果的小集合,以及最终所有符合条件的集合,返回的也就是一个二维数组.

     /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum($candidates, $target) {
        $out=[];
        $res=[];
       $this->helper($candidates,$target,0,$out,$res);
        return $res;
    }
    function helper($candidates,$target,$index,&$out,&$res){
        if($target<0) return ;
        if($target==0) {
             array_push($res,$out);
            return ;
        }
           
        for($i=$index;$i<count($candidates);$i++){
            array_push($out,$candidates[$i]);
            $this->helper($candidates,$target-$candidates[$i],$i,$out,$res);
            array_pop($out);
        }
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php



点赞 取消点赞 收藏 取消收藏

<< 上一篇: Leetcode PHP题解--D80 182. Duplicate Emails

>> 下一篇: Leetcode PHP题解--D81 520. Detect Capital