Backtracking - Permutations, Combinations, Subsets
ראיון ב-Apple TLV, 2023: "Generate all valid parentheses combinations for n pairs." כ-80% מהמועמדים שמגיעים עם DFS גנרי מתבלבלים. 20% שמבינים Backtracking כ-Template - כותבים פתרון ב-12 דקות. ה-Template הוא: choose, explore, unchoose.
Backtracking הוא Pattern שמרגיש "מסובך" כי הוא רקורסיבי ויש לו State שמשתנה. אבל ברגע שמפנימים את ה-Template - choose → explore → unchoose - ורואים שהוא קבוע, הפחד מתפוגג. כל שאלת Backtracking היא וריאציה על אותה שאלה: מה אנחנו בוחרים? מה תנאי הסיום? מה תנאי ה-Pruning?
Backtracking הוא Brute Force מסודר. הרעיון: בונים פתרון צעד אחר צעד, ואם מגיעים למצב שאי אפשר להמשיך - חוזרים לאחור (Backtrack) ומנסים אפשרות אחרת. יש Template אחד שמכסה 95% מהשאלות.
הסוד שמועמדים שמכירים Backtracking מבינים: ה-Template לא משתנה - רק ה-Parameters. כשעוברים מSubsets לPermutations לGenerate Parentheses, ה-choose → explore → unchoose נשאר אחיד. מה שמשתנה הוא: מה הבחירות האפשריות? מה תנאי הסיום? מה Pruning Conditions? שלוש שאלות אלה - התשובה לכל שאלת Backtracking.
בלי Template ברור, Backtracking מרגיש "כל שאלה חדשה." עם Template - כל שאלה חדשה היא פשוט "מה choose, explore, unchoose בהקשר הזה?" ה-Cognitive Load עובר מ"איך לפתור" ל"מה הפרמטרים של הTemplate הידוע."