本篇內(nèi)容主要講解“如何用php回溯算法計(jì)算組合總和”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“如何用php回溯算法計(jì)算組合總和”吧!

創(chuàng)新互聯(lián)公司專業(yè)為企業(yè)提供莊河網(wǎng)站建設(shè)、莊河做網(wǎng)站、莊河網(wǎng)站設(shè)計(jì)、莊河網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、莊河企業(yè)網(wǎng)站模板建站服務(wù)，10余年莊河做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

給定一個(gè)數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。

candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。

說(shuō)明：

所有數(shù)字（包括目標(biāo)數(shù)）都是正整數(shù)。 解集不能包含重復(fù)的組合。

實(shí)例

輸入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集為:[
 [1, 7],
 [1, 2, 5],
 [2, 6],
 [1, 1, 6]]

解題思路

直接參考回溯算法團(tuán)滅排列/組合/子集問(wèn)題。

代碼

class Solution {
 
    /** * @param Integer[] $candidates * @param Integer $target * @return Integer[][] */
 
    public $res = [];
 
    function combinationSum2($candidates, $target) {
 
        sort($candidates);   // 排序
 
        $this->dfs([], $candidates, $target, 0);
 
        return $this->res;
 
    }
 
    function dfs($array, $candidates, $target, $start) {
 
        if ($target < 0) return;
 
        if ($target === 0) {
 
            $this->res[] = $array;
 
            return;
 
        }
 
        $count = count($candidates);
 
        for ($i = $start; $i < $count; $i++) {
 
            if ($i !== $start && $candidates[$i] === $candidates[$i - 1]) continue;
 
            $array[] = $candidates[$i];
 
            $this->dfs($array, $candidates, $target - $candidates[$i], $i + 1);//數(shù)字不能重復(fù)使用,需要+1
 
            array_pop($array);
 
        }
 
    }}

到此，相信大家對(duì)“如何用php回溯算法計(jì)算組合總和”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！