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

2019-6-6 星期四 开始吧

上一题链接Leetcode基础刷题之PHP解析(39. Combination Sum)

题目描述

给定一个数组和一个目标数，求所有加起来等于目标数的组合，这个39题的第二版。它的规则和39有一点不同的是每一个结果集中目标的数只能使用一次，不能重复的使用。

题目分析

这里我们还是可以复用上一题的code，只需要在代码中把重复的结果，以及数字复用的的情况处理一下即可。

 /**
     * @param Integer[] $candidates
     * @param Integer $target
     * @return Integer[][]
     */
    function combinationSum2($candidates, $target) {
        sort($candidates);
        $res=[];
        $out=[];
        $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++){
            if($i>$index && $candidates[$i]==$candidates[$i-1]) continue;
            array_push($out,$candidates[$i]);
            $this->helper($candidates,$target-$candidates[$i],$i+1,$out,$res);
            array_pop($out);
        }
     }

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