Hello!
Cette semaine on se retrouve pour un problème de Backtracking, le 39. Combination Sum 🔗.
Voilà l’énoncé:
Étant donné une liste d’entiers distincts
candidates
et un entier cibletarget
,
—> Retournez la liste de l’ensemble des combinaisons uniques où la somme des nombres choisis est égale à l’entier cible.
Le même entier peut être choisi parmi les candidats un nombre illimité de fois.
Deux combinaisons sont uniques si la fréquence d'au moins un des nombres choisis est différente.
Hint - Les expressions du type “générer l’ensemble des combinaisons” invitent à approcher le problème par le Backtracking.
Le Backtracking permet d’explorer un espace de recherche, à la façon d’une DFS, en revenant sur ses pas (to backtrack) lorsque la branche explorée ne vérifie pas les contraintes du problème.
Comment s’y prendre ?
On parcourt l’espace des solutions (les entiers proposés dans la liste candidates
) en construisant au fur et à mesure une liste des entiers rencontrés.
Si la somme de cette liste est égale à la valeur cible, alors on ajoute la liste actuelle à une variable globale des solutions.
Ci-dessous une implémentation en Python:
class Solution: | |
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: | |
solutions: List[List[int]] = [] | |
n: int = len(candidates) | |
candidates.sort() # Helps us to prune the search space (cf line 15) | |
def backtrack(sum_: int, start_idx: int, cur_list: List[int]) -> None: | |
if sum_ == target: # Goal - base case | |
solutions.append(cur_list) | |
return | |
for i in range(start_idx, n): | |
if sum_ + candidates[i] <= target: | |
backtrack(sum_ + candidates[i], i, cur_list + [candidates[i]]) # Explore further the solution space | |
else: | |
return # Pruning - no need to explore further if the sum is above the target value. | |
backtrack(0, 0, []) | |
return solutions |
Optimisation
Ici, on parcourt l’espace de solution en triant au préalable les candidates
par ordre croissant.
Cela nous permet d’interrompre le parcours d’une branche si l’on se rend compte que la somme est au-delà de la valeur cible (c.f. ligne 15).
C’est le concept de pruning: accélérer le parcours de l’espace de solutions en défaussant des branches dont on est certain qu’elles ne mèneront pas à une résolution.
Étude de la complexité
L’analyse de la complexité n’est pas évidente, l’onglet solution de Leetcode propose des éléments de réponse éclairants. Un peu de notation:
Posons N le nombre de candidats, T la valeur cible (target) et M pour la valeur minimale parmi les candidats.
Complexité en mémoire
O(T/M)
La profondeur maximale de la call stack nécessaire pour aller au plus profond de la DFS est de T/M: cela correspond au cas où l’on ajoute le plus petit élément des candidates
M autant de fois nécessaire pour arriver à T.
La taille maximale de la notre liste cur_list
est donc T/M.
Complexité temporelle
O(N^[(T/M) +1] + Nlog(N))
Le Nlog(N) est le coût du tri initial.
Pour le terme en O(N^[T/M +1]) :
Pour estimer la complexité du Backtracking, on peut se baser sur la DFS équivalente: Pour chaque entier de la liste
candidates
, on peut explorer au maximum T/M nœuds à partir de ce nœud. Le nombre de nœuds dans un arbre N-aire de hauteur T/M est N^(T/M + 1).
Interview Pro Tips 💡
Il est courant que les questions posées dans un entretien technique d’un GAFA soient brèves et manquent d’éléments pour pouvoir la résoudre correctement.
La première étape consiste à lever toutes les ambiguïtés autour de la question. Prenons l’hypothèse:
Les éléments du tableau
candidates
sont tous distincts.
Sur Leetcode, c’est une donnée de l’énoncé précisée explicitement dans les contraintes en bas de page.
Typiquement, cette hypothèse pourrait être omise par l’examinateur lors d’une interview afin de voir si le candidat prend l’initiative de rassembler toutes les informations nécessaires pour aborder le problème convenablement.
👉 TL;DR:
Posez des questions pour être certains de comprendre le problème qu’il est demandé de résoudre.
Rendez explicite les hypothèses sur lesquelles se base votre raisonnement.
Ressources utiles
Pour une approche exhaustive du Backtracking, je recommande l’ouvrage de Skiena:
Skiena, S. S. (2009). The Algorithm Design Manual. Springer Science & Business Media.
Notamment le Chapitre 7 - Combinatorial Search and Heuristic Methods, la section 7.1 Backtracking (page 231)
Cet article medium sur le backtracking donne aussi une très bonne explication: Leetcode Pattern 3 | Backtracking | by csgator
La vidéo de la session est disponible sur Youtube:
La semaine prochaine on pousse la barre un peu plus haut sur le Backtracking en s’attaquant à un problème HARD 🙈 le 140. Word Break II.
Comme d’habitude, on se donne rendez-vous à 09h30 samedi matin prochain sur notre channel Twitch pour traiter ce problème en live ⏱
See ya!
Photo de thumbnail de Brady Knoll trouvée sur Pexels