Comment utiliser l'algorithme de backtracking pour résoudre le problème de sous-ensemble en PHP

L'algorithme de retour en arrière est en fait un processus de tentative de recherche similaire à l'énumération. Il recherche principalement la solution au problème pendant le processus de tentative de recherche. Lorsqu'il s'avère que les conditions de solution ne sont plus remplies, il « fait marche arrière » et revient à. essayez d'autres chemins. La méthode de backtracking est une méthode de recherche d'optimisation qui recherche en avant en fonction des conditions d'optimisation pour atteindre l'objectif.

Lorsque vous explorez une certaine étape et constatez que le choix initial n'est pas optimal ou ne peut pas atteindre l'objectif, vous prendrez du recul et choisirez à nouveau cette technique consistant à revenir en arrière et à réessayer lorsque ce n'est pas le cas. Le travail est la méthode de retour en arrière, et une certaine méthode qui satisfait aux conditions de retour en arrière. Le point de cet état est appelé le « point de rétrospection ». De nombreux problèmes complexes et à grande échelle peuvent utiliser la méthode du backtracking, connue sous le nom de « méthode universelle de résolution de problèmes ».

Subsets

Étant donné un ensemble de tableaux d'entiers numériques sans éléments en double, renvoie tous les sous-ensembles possibles (ensembles de puissance) du tableau.

Remarque : L'ensemble de solutions ne peut pas contenir de sous-ensembles répétés.

Exemple :

输入: nums = [1,2,3]
输出:[  [3],  
[1],  
[2],  
[1,2,3], 
[1,3],  
[2,3], 
[1,2],  
[]]

Idée de résolution de problème 1

Référence directe au problème de permutation/combinaison/sous-ensemble d'élimination de groupe d'algorithme de backtracking

Code

class Solution {
    public $result = [];
    /** 
    * @param Integer[] $nums 
    * @return Integer[][] 
    */
    function subsets($nums) {
       $this->dfs(0, $nums, []);
       return $this->result;
    }
    // 递归部分 
    function dfs($start, $nums, $array){
        $this->result[] = $array;
        for ($i = $start; $i < count($nums); $i++) {
            $array[] = $nums[$i];
            $this->dfs($i + 1, $nums, $array);
            array_pop($array);
        }
    }}

Idée de résolution de problème 2 Méthode itérative

L'initialisation le résultat est deux tableaux de dimensions vides qui parcourent chaque élément du tableau donné et, à chaque itération, traitent l'ensemble de résultats. Chaque élément du jeu de résultats ajoute le nombre parcouru et la longueur du jeu de résultats continue d'augmenter.

class Solution {
  /** 
  * @param Integer[] $nums 
  * @return Integer[][] 
  */
    function subsets($nums) {
        $result = [];
        $result[] = [];
        $numsCount = count($nums);
        for ($i = 0; $i < $numsCount; $i++) {
            $resultCount = count($result);
            for ($j = 0; $j < $resultCount; $j++) {
                $tmp = $result[$j];
                $tmp[] = $nums[$i];
                $result[] = $tmp;
            }
        }
        return $result;
    }}

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!