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
No Comments