力扣216题的问题
来源:8-5 回溯法解决组合问题的优化
向往那片天空
2020-12-14
波波老师,我的递归解法这样的,帮我看看,算不算是回溯呢?
class Solution {
/**
* @param Integer $k
* @param Integer $n
* @return Integer[][]
*/
function combinationSum3($k, $n) {
$nArr=range(1,9);//获取1-9组合
return $this->getCombinationSum($k,$n,$nArr);
}
function getCombinationSum($k,$n,$nArr){
sort($nArr);//排序数组
foreach($nArr as $key=>$v){
if($v>$n){
$nArr=array_slice($nArr,0,$key);//剪枝
break;
}
}
$ret=[];
if($k==1){//递归终止
foreach($nArr as $item){
if($item==$n)
$ret[]=[$item];
}
return $ret;
}
foreach($nArr as $key=>$v){
unset($nArr[$key]);
$res=$this->getCombinationSum($k-1,$n-$v,$nArr);//递归
foreach($res as $vv){//处理返回结果
array_unshift($vv,$v);
$ret[]=$vv;
}
}
return $ret; //返回结果
}
}
写回答
1回答
-
算。
回溯本质就是在解空间暴力搜索,只要是这个思路,都是回溯。
继续加油!:)
012020-12-14
相似问题