2019-06-06 吴亲库里 库里的深夜食堂
给定一个数组和一个目标数,求所有加起来等于目标数的组合,这个39题的第二版。它的规则和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);
}
}