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

递归第二天

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

题 目 描 述

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

题 目 分 析

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

/**
     * @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