Backtracking : explorer un arbre de décisions

Générer toutes les combinaisons, permutations ou sous-ensembles : à chaque étape on choisit, on explore, puis on annule.

Toute récursion a besoin d'un cas de base, d'une relation de récurrence et d'appels qui progressent vers le cas de base (sinon : stack overflow). Le backtracking ajoute l'étape « annuler le choix » pour explorer les alternatives.

Le squelette#

fonction explorer(état):
    si état est une solution : l'enregistrer
    pour chaque choix possible :
        appliquer le choix
        explorer(état)
        annuler le choix          <- le « backtrack »

Tous les sous-ensembles#

À chaque élément, deux décisions : le prendre ou non. Il y a 2ⁿ sous-ensembles : la complexité est O(2ⁿ) inévitable, puisqu'on génère toute la sortie.

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  const current: number[] = [];

  function explore(start: number): void {
    result.push([...current]);                      // chaque état est une solution
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);                        // choisir
      explore(i + 1);                               // explorer
      current.pop();                                // annuler
    }
  }

  explore(0);
  return result;
}

Élagage (pruning)#

Dès qu'une branche ne peut plus mener à une solution (contrainte dépassée, somme trop grande), on la coupe immédiatement. Cela transforme parfois un temps exponentiel en quelque chose de praticable.

Cas pratique : « somme des combinaisons » : si le total courant dépasse déjà la cible et que les valeurs sont positives, arrêtez la branche. Triez d'abord les candidats pour couper aussi les suivants d'un coup.

Pour aller plus loin#

• Backtracking: Permutations (Leetcode 46) — NeetCode