Backtracking : explorer un arbre de décisions
Générer toutes les combinaisons, permutations ou sous-ensembles sans tout écrire à la main.
La récursion résout un problème en le décomposant en sous-problèmes identiques mais plus petits, avec un cas de base qui arrête la descente. Chaque appel doit progresser vers ce cas de base, sinon on obtient une boucle infinie (stack overflow).
Trois ingrédients à identifier avant de coder : le cas de base (quand s'arrêter), la relation de récurrence (comment le problème de taille n se ramène à un problème plus petit), et ce que retourne chaque appel.
Le backtracking est une récursion qui explore un arbre de décisions : à chaque étape, on fait un choix, on récurse, puis on « annule » ce choix (backtrack) pour essayer les autres possibilités. Utile pour générer toutes les combinaisons, permutations ou sous-ensembles.
Structure typique : une fonction qui prend un état partiel, vérifie si c'est une solution complète (auquel cas on l'ajoute aux résultats), sinon essaie chaque choix possible — ajouter le choix à l'état, récurser, puis retirer le choix avant d'essayer le suivant.
Élagage (pruning) : dès qu'on sait qu'une branche ne peut plus mener à une solution valide (ex : une contrainte est déjà dépassée), on arrête de l'explorer immédiatement plutôt que de continuer inutilement — ça peut transformer un temps d'exécution exponentiel en quelque chose de praticable.
Vidéo
Backtracking: Permutations (Leetcode 46) — NeetCodeQuiz
1. Que doit obligatoirement contenir une fonction récursive pour éviter une boucle infinie ?
2. Le backtracking se caractérise par :
3. Le pruning (élagage) sert à :
4. Le backtracking est un bon candidat quand l'énoncé demande :