力扣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回答

liuyubobobo

2020-12-14

算。


回溯本质就是在解空间暴力搜索,只要是这个思路,都是回溯。


继续加油!:)

0
1
向往那片天空
非常感谢!
2020-12-14
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7410 学习 · 1150 问题

查看课程