Comment calculer la somme combinée à l'aide de l'algorithme de backtracking en PHP

Étant donné un tableau de candidats et un nombre cible, trouvez toutes les combinaisons de candidats qui peuvent faire en sorte que la somme des nombres soit cible. Que devons-nous faire à ce moment-là ? Aujourd'hui, je vais vous guider à travers cela.

Donner Définissez un tableau de candidats et un nombre cible, et recherchez toutes les combinaisons de candidats pouvant constituer la somme des nombres cibles.

Chaque numéro dans

candidat ne peut être utilisé qu'une seule fois dans chaque combinaison.

Remarque :

Tous les nombres (y compris le nombre cible) sont des entiers positifs. L'ensemble de solutions ne peut pas contenir de combinaisons en double.

Exemple 1 :

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

Exemple 2 :

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:[  
[1,2,2],  
[5]]

Idées de résolution de problèmes

Référence directe au problème de permutation/combinaison/sous-ensemble annihilant le groupe d'algorithmes de retour en arrière

Code

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);//数字不能重复使用,需要+1
            array_pop($array);
        }
    }}

Extra :

Étant donné un tableau de candidats sans éléments en double et un nombre cible cible, trouvez toutes les combinaisons de candidats qui peuvent faire de la somme des nombres une cible.

Les nombres de candidats peuvent être sélectionnés à plusieurs reprises sans limite.

La différence est que les sélections répétées sont autorisées et elles sont résolues en effectuant deux modifications basées sur la question précédente.

class Solution {
    /** * @param Integer[] $candidates * @param Integer $target * @return Integer[][] */
    public $res = [];
    function combinationSum($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
            array_pop($array);
        }
    }}

Extra :

Trouvez toutes les k combinaisons de nombres dont la somme est n. Seuls les entiers positifs de 1 à 9 sont autorisés dans la combinaison, et il n'y a aucun nombre en double dans chaque combinaison.

Limiter le nombre d'éléments dans le plan sélectionné

class Solution {
    public $res = [];
    /** * @param Integer $k * @param Integer $n * @return Integer[][] */
    function combinationSum3($k, $n) {
        $this->dfs([], [1,2,3,4,5,6,7,8,9], $n, 0, $k);
        return $this->res;
    }
    function dfs($array, $candidates, $n, $start, $k) {
        if ($n < 0) return;
        if ($n === 0 && count($array) === $k) {
            $this->res[] = $array;
            return;
        }
        for ($i = $start; $i < 9; $i++) {
            if ($i !== $start && $candidates[$i] === $candidates[$i - 1]) continue;
            $array[] = $candidates[$i];
            $this->dfs($array, $candidates, $n - $candidates[$i], $i + 1, $k);
            array_pop($array);
        }
    }}

Apprentissage recommandé : tutoriel vidéo php

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!