Backtrackingdecision tree · choose → explore → unchoose · pruning
في فصول الـ recursion والـ trees شفت دالة بتنادي نفسها وبترسم شجرة calls. هنا هنستخدم الشجرة دي عشان نجرّب كل الاحتمالات بنظام: تختار، تكمّل، ولما تخلص ترجع في اختيارك وتجرّب اللي بعده. ده الـ backtracking.
هتطلع من الفصل ده وإنت عارف
- تشوف أي مسألة "كل الاحتمالات" على إنها decision tree، وتعرف كل node فيها معناها إيه.
- تكتب template الـ choose → explore → unchoose من دماغك، وتعرف ليه
path.pop()لازم، وليه بنسجّل[...path]مشpath. - تفرّق بين subsets و combinations و permutations: إمتى
start، وإمتىused[]، وإزاي تشيل التكرار بـ sort وi > start. - تحل Subsets و Permutations و Combination Sum و Subsets II و Letter Combinations و Word Search، وتفهم N-Queens.
- تحسب عدد الاحتمالات (2ⁿ و n!) وتعرف من الـ constraints هل الحل هيعدّي.
ليه Backtracking؟
في فصل الـ Recursion شفت إن كل call بيفتح call تاني لحد الـ base case. هنا هنستغل ده عشان نعمل حاجة الـ loops العادية مش بتعرف تعملها.
خد المسألة دي: عندك [1, 2, 3] وعايز كل الـ subsets: [] و [1] و [2] و [3] و [1, 2] و [1, 3] و [2, 3] و [1, 2, 3]. كل عنصر ليه قرارين: تاخده أو تسيبه. فمع 3 عناصر تقدر تكتبها بـ 3 loops جوه بعض:
طب لو n = 10؟ هتكتب 10 loops؟ ولو n جاية من الـ input؟ مستحيل تكتب عدد loops متغيّر بإيدك. الـ key insight هنا إن كل call في الـ recursion بيعمل شغل loop واحدة، وبينادي نفسه عشان يعمل الـ loop اللي جواها. فالـ recursion بتعمل nested loops بأي عمق، والعمق ده بيتحدد وقت الـ runtime.
- كل call ليه نسخته من المتغيرات. لو
go(0)نادتgo(1)، الـiجوهgo(1)= 1، والـiبتاعgo(0)لسه 0 ومستني. - لما الـ call يخلص، بيرجع لنفس السطر اللي اتنادى منه ويكمّل اللي بعده. ده اللي هيخلّينا "نرجع لورا" ونجرّب اختيار تاني.
- الـ call stack فيه الـ calls اللي لسه ما خلصتش. اللي فوق شغال، والباقي waiting. هتشوفه في الـ animations.
الـ decision tree
ارسم القرارات كشجرة: الـ root = "لسه ما قررتش حاجة". من كل node فرعين: الشمال = سبت العنصر، اليمين = أخدته. كل node هي partial choice: قررت في أول كام عنصر والباقي لسه. ولما توصل لعمق n تبقى leaf، يعني subset كاملة.
pathهو array واحدة بس بتمثّل الـ node اللي إحنا واقفين عندها. كل الـ calls بتشاركها، وده سبب كل التفاصيل اللي جاية.go(i)معناها: "قررت فيnums[0..i-1]، ودلوقتي هقرر فيnums[i]". يعنيi= عمق الـ node.- ليه
nums.lengthمشnums.length - 1؟ لماi = 2لسه ما قررناش في الـ 3. جرّبتها بـ- 1: بتطلع 4 subsets بس[[], [2], [1], [1, 2]]، ومفيش ولا واحدة فيها 3. - بنسجّل copy من الـ path، لأنه هيتغيّر بعد كده. التفاصيل في قسم الـ template.
- ده الـ base case. من غيره
go(4)وgo(5)… لحدMaximum call stack size exceeded. - Branch 1: نسيب
nums[i]. الـ path ما بيتغيّرش. - Branch 2: ناخده وننزل.
- أهم سطر. الـ invariant: كل call بيرجّع الـ path زي ما استلمه، لأن اللي نادانا مستني يلاقيه زي ما ساب.
اتفرّج على الشجرة وهي بتتبني. الأصفر = الـ node الحالية، والأوراق الخضرا اتسجّلت، والرقم تحتها ترتيب التسجيل:
15 node، منهم 8 leaves = 8 subsets. وترتيب الـ calls هو نفسه DFS على الشجرة: بننزل للآخر، ونرجع خطوة، ونجرّب الفرع التاني.
طب إزاي تعرف من كلام المسألة إنها backtracking أصلًا؟
إزاي تعرفه من المسألة
أوضح signal كلمة "كل": كل الـ subsets، كل الترتيبات، كل الطرق. والتانية إن الـ constraints صغيرة جدًا (n ≤ 10 أو n ≤ 15). المسألة بتقولك من غير ما تقول: "جرّب كله".
لو المطلوب عدد الطرق بس، أو أحسن قيمة، فغالبًا فيه حل أسرع بكتير بالـ Dynamic Programming. الـ backtracking بيطلّع الإجابات نفسها واحدة واحدة، فلو عددها مليارات مش هيلحق.
| النوع | بنسجّل إمتى | الـ loop بتبدأ منين | الـ call الجاي | مسائل |
|---|---|---|---|---|
| Subsets | في كل node | start | backtrack(i + 1) | 78 |
| Combinations | لما الطول k أو المجموع target | start | i + 1، أو i لو التكرار مسموح | 77، 39 |
| Permutations | لما path.length === n | 0 مع used[] | backtrack() | 46 |
| Input فيه تكرار | زي اللي فوق | sort الأول، وبعدين skip | زي اللي فوق | 90، 40، 47 |
| Grid / board | لما تطابق آخر حرف أو تحط آخر قطعة | 4 directions أو كل عمود | الخانة اللي جنبك أو الصف اللي بعده | 79، 51 |
flowchart TD
A["Generate ALL answers?"] --> B{"Does order matter?"}
B -- "yes: [1,2] is not [2,1]" --> P["Permutations: loop from 0 + used[]"]
B -- "no" --> C{"Can you reuse an element?"}
C -- "no" --> S["Subsets / combinations: loop from start, recurse with i + 1"]
C -- "yes" --> R["Combination sum: loop from start, recurse with i"]
S --> D{"Duplicate values in the input?"}
R --> D
P --> D
D -- "yes" --> K["Sort first, then skip equal values at the same level"]
D -- "no" --> OK["Template as is"]
السؤالين المهمين: هل الترتيب فارق؟ وهل مسموح تعيد نفس العنصر؟
كل الأنواع دي ليها template واحد بس. يلا نفصّصه سطر سطر.
الـ template: choose → explore → unchoose
قبل ما تكتب أي سطر، جاوب على تلات أسئلة:
- الـ path فيه إيه؟ الـ partial choice اللي بتبنيه: عناصر، حروف، أماكن queens.
- إمتى الـ path يبقى إجابة كاملة؟ ده الـ base case: طوله
n، المجموع صفر، وصلت لآخر صف. - إيه الـ choices المتاحة، وإيه الممنوع؟ دي الـ loop وشروطها.
- ليه path واحدة مشتركة؟ لو كل call عمل array جديدة، ده copy بـ O(n) في كل node. مع array واحدة الـ
pushوالـpopالاتنين O(1). الـ trade-off: لازم ترجّع كل حاجة بإيدك (سطر 13). state= اللي محتاجه عشان تعرف إنت فين في الشجرة:start، أوremain، أو رقم الصف، أو(r, c, k).- الـ base case، بيختلف حسب المسألة:
path.length === n، أوremain === 0، أو مفيش شرط خالص زي الـ subsets. - Copy.
[...path]بتعمل array جديدة بالعناصر اللي دلوقتي. تحت هتشوف بالـ animation إيه اللي بيحصل من غيرها. - Early return: الإجابة كاملة، مفيش داعي ننزل. في Letter Combinations لو نسيته هتقرا
digits[i]بعد آخر الـ string وتضرب TypeError. - Pruning: لو عارف من دلوقتي إن الـ choice ده مش هيوصل، ما تنزلش فيه. ده بيشيل subtree كامل مرة واحدة.
- Choose وبعدين explore: لما الـ call ده يرجع، يبقى جرّبنا كل الإجابات اللي بتبدأ بالـ path ده.
- Unchoose: القاعدة الذهبية: أي حاجة غيّرتها في الـ choose، ترجّعها هنا بالعكس. لو غيّرت حاجتين، ترجّع الاتنين.
ليه path.pop() لازم؟
عشان الـ path واحدة، والإخوات في الشجرة بيستخدموها ورا بعض. لما ترجع من [1, 2] وتروح لـ [1, 3]، لازم الـ 2 تكون اتشالت. ده ناتج Subsets على [1, 2, 3] من غير pop:
ليه [...path] مش path؟
الـ array في JS object. res.push(path) مش بتحط صورة من الـ path، بتحط reference للـ array نفسها. فكل خانات res بتشاور على نفس الـ array، وأي push أو pop بعد كده بيظهر فيهم كلهم.
[...path]. لكن لو كتبت في الكشكول "شوف السبورة"، آخر اليوم هتلاقيها ممسوحة. ده path.
شوف الـ bug على [1, 2]. صف res بيعرض اللي في كل خانة دلوقتي:
الحل: res.push([...path]) أو path.slice(). والـ copy دي O(n)، وده جزء من الـ complexity. ملاحظة: لو الـ path string مش محتاج copy، لأن الـ strings في JS immutable: path + 'a' بيعمل string جديد. هتشوف ده في Letter Combinations.
لو حطيت path.pop() قبل backtrack(...) بدل بعدها، إيه اللي هيحصل؟
- مفيش فرق، الاتنين بيتنفذوا في الآخر
- الـ path هيرجع زي ما كان قبل ما ننزل، فالـ call اللي تحت مش هيشوف الـ choice اللي لسه عاملينه
- هيطلع error لأن الـ path فاضي
- الحل هيبقى أسرع
الترتيب هو المعنى كله: نضيف، بعدين ننزل والـ choice موجود، بعدين نشيله لما نرجع.
يلا نطبّق الـ template على أول مسألة حقيقية: Subsets، بس بشكل شجرة أعمّ من "ناخد ولا نسيب".
مثال محلول 1: Subsets
عندك array أرقامها كلها مختلفة. رجّع كل المجموعات الجزئية (الـ power set). نفس المجموعة ما تتكررش، والترتيب مش مهم.
نفكّر فيها مع بعض
- افهم المطلوب: subset مالهاش ترتيب:
[1, 2]هي[2, 1]، فتطلع مرة واحدة. - Brute force: شجرة "ناخد ولا نسيب" = O(n · 2ⁿ)، ومفيش أحسن منها لأن الـ output نفسه 2ⁿ subset. السؤال هنا "إزاي أكتب template أقدر أعيد استخدامه".
- الـ key insight: بدل "ناخد ولا نسيب"، نسأل في كل node: "العنصر الجاي إيه؟"، بشرط إنه ييجي بعد آخر عنصر أخدناه. كده كل subset بتطلع بترتيب الـ indices:
[1, 2]آه، و[2, 1]عمرها. - الـ start index: أول index مسموح نختار منه. الـ root بيبدأ بـ 0، ولو اخترت
nums[i]الـ child بياخدi + 1. - بنسجّل إمتى؟ في الشكل ده كل node subset صح، فبنسجّل أول ما ندخل أي call. والـ edge case: array فاضية الإجابة
[[]].
start= أول index مسموح في الـ node دي، وهو اللي بيمنع التكرار.- مفيش
if. كل node subset، فبنسجّل على طول. والـ base case مستخبّي: لماstart === nums.lengthالـ loop مش بتلف والدالة بترجع لوحدها. - ليه
i = startمش 0؟ من 0 هتختار نفس العنصر تاني:[1, 1, 1, …]لحد stack overflow. وi < nums.lengthمش<=، وإلا هتعملpush(undefined). i + 1مشstart + 1، أشهر غلطة هنا. الـ child يبدأ بعد اللي لسه مختاره. جرّبتstart + 1: بتطلع 16 array بدل 8، فيهم[2, 2]و[3, 2].- Unchoose، عشان الـ
iالجاية تبدأ من نفس الـ path.
الخانات الباهتة في nums هي اللي قبل start (ممنوعة في الـ call ده)، والرقم على كل edge هو العنصر اللي اتضاف:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [] | [[]] | الـ loop مش بتلف، بس سطر 5 بيسجّل []. |
| [5] | [[], [5]] | أبسط شجرة: root و child واحد. |
| 10 عناصر | 1024 subset | 2¹⁰، أقصى n في المسألة. |
التعقيد: 2ⁿ node، وكل node بتعمل copy لحد n: O(n · 2ⁿ) وقت. والـ memory غير الـ output: O(n) للـ path والـ stack.
هنا الترتيب ما كانش فارق. طب لو [1, 2] و [2, 1] إجابتين مختلفتين؟
مثال محلول 2: Permutations
عندك array أرقامها مختلفة. رجّع كل الترتيبات الممكنة ليها.
الجديد هنا إن الترتيب فارق، فالـ start index مش هينفع، ومحتاجين طريقة تانية نعرف بيها مين اتاخد.
نفكّر فيها مع بعض
- ليه الـ start مش هينفع؟ الـ start بيقول "من اللي بعدي بس". لو اخترت 3 الأول مش هتقدر ترجع للـ 1، فـ
[3, 1, 2]عمرها ما هتطلع. جرّبتها: بتطلّع[[1, 2, 3]]بس. - الـ key insight: في كل خانة، أي عنصر لسه ما اتاخدش ينفع. فنحتفظ بـ
used[i]= true لوnums[i]في الـ path دلوقتي. - ليه مش
path.includes(x)؟ ده O(n) في كل check بدل O(1)، وبيبوظ مع الأرقام المتكررة لأنusedشغالة بالـ index مش بالقيمة. - بنسجّل لما
path.length === nums.length. والـ unchoose بقى حاجتين، لأن الـ choose غيّر حاجتين.
fill(false)مهمة:new Array(n)لوحدها بتعمل empty slots قيمتهاundefined. هتشتغل لأنundefinedfalsy، بس الـ fill أوضح.- مفيش parameter: الـ state كله في
pathوused، والعمق هوpath.length. - من 0 كل مرة، لأن أي عنصر مش مستخدم ينفع في الخانة الجاية، حتى لو الـ index بتاعه أصغر.
- اللي في الـ path ما يتكررش في نفس الـ permutation.
- Unchoose الاتنين. لو نسيت
used[i] = false، كل العناصر هتفضل true بعد أول permutation، والنتيجة permutation واحدة بس (جرّبتها).
الخانات الخضرا في nums هي اللي used بتاعها true:
التعقيد: n! leaf، وكل leaf بتعمل copy بـ n: O(n · n!). الـ memory O(n). وده سبب إن الـ n في المسألة لحد 6 بس (6! = 720).
nums[i] لو زي nums[i - 1] و used[i - 1] بـ false. يعني النسخ المتساوية تتاخد دايمًا بالترتيب.
لحد دلوقتي كل عنصر بيتاخد مرة واحدة بالكتير. طب لو مسموح تعيده، ومحتاج توقف عند مجموع معيّن؟
مثال محلول 3: Combination Sum
عندك أرقام موجبة مختلفة candidates و target. طلّع كل المجموعات اللي مجموعها target، ومسموح تستخدم نفس الرقم أكتر من مرة. نفس الأرقام بترتيب مختلف = نفس المجموعة.
الجديد هنا حاجتين صغيرين: الـ call بياخد i مش i + 1 عشان التكرار، وأول pruning حقيقي بيقطع فروع كاملة.
نفكّر فيها مع بعض
- combination ولا permutation؟
[2, 4]=[4, 2]، يعني الترتيب مش فارق: template الـstart. - التكرار مسموح: بدل
backtrack(i + 1)نناديbacktrack(i): "خد نفس العنصر تاني لو عايز، بس عمرك ما ترجع لعنصر قبله". ده بيسمح بـ[2, 2, 2]ويمنع[4, 2]. - الـ state:
(start, remain)، وremain= الباقي للـ target. بنسجّل لماremain === 0. - Pruning: لو رتّبنا، وقابلنا رقم أكبر من
remain، يبقى هو وكل اللي بعده أكبر.breakمشcontinue. - ليه الـ recursion بتخلص؟ لأن كل الأرقام موجبة، فـ
remainبيقل في كل level. لو كان فيه صفر،backtrack(i)هيلف للأبد.
- الـ sort عشان الـ
breakفي سطر 11. والـ comparator لازم، من غيره JS بترتّب الأرقام كـ strings ([10, 9, 2]تبقى[10, 2, 9])، والـ break هيقطع فروع فيها إجابات. - وصلنا للـ target بالظبط. مش محتاجين حالة
remain < 0، لأن سطر 11 بيمنعنا ننزل في أي فرع هيعدّي. - ليه
break؟ الـ array مترتبة، فكل اللي بعدcandidates[i]أكبر منه.continueهيدّي نفس النتيجة، بس هيلف على عناصر عارفين إنها مش هتنفع. - بـ
iمشi + 1: ده الفرق الوحيد عن الـ subsets. بـi + 1هتطلع[[2, 4]]بس. - بنعمل pop للـ path بس.
remainمش محتاج نرجّعه، لأنه parameter: كل call معاه نسخته.
الرقم تحت كل node هو remain. الـ nodes الحمرا هي الفروع اللي الـ pruning قطعها:
| Input | المتوقع | ليه الحالة دي مهمة |
|---|---|---|
| [5], 3 | [] | أول رقم أكبر من الـ target، break على طول. |
| [3, 2, 4], 6 | [[2,2,2],[2,4],[3,3]] | مش مترتبة: من غير سطر 2 الـ break هيقطع غلط. |
| [7], 7 | [[7]] | رقم واحد بيساوي الـ target. |
التعقيد: أقصى عمق target / min، وكل node ليها لحد n فرع، فالـ worst case O(n^(target / min)). في الواقع الـ pruning بيقطع أغلبها.
كل الأمثلة اللي فاتت الأرقام فيها مختلفة. لو الـ input فيه تكرار، الإجابات نفسها هتتكرر. إزاي نمنع ده؟
مثال محلول 4: Subsets II (فيه تكرار)
زي Subsets، بس الـ array ممكن يكون فيها أرقام متكررة. رجّع كل الـ subsets من غير ما أي واحدة تتكرر.
الجديد هنا سطر واحد بيمنع الإجابات المكررة، وهتستخدمه في أي مسألة input فيها تكرار.
نفكّر فيها مع بعض
- Subsets زي ما هو؟ على
[1, 2, 2]هيطلّع[1, 2]مرتين و[2]مرتين: 8 بدل 6. - التكرار بييجي منين؟ node واحدة اختارت مرة الـ 2 اللي عند index 1، ومرة اللي عند index 2. دول إخوات في نفس الـ level، ونفس القيمة، فالـ subtrees اللي تحتهم متطابقة.
- الحل: sort عشان المتساويين يبقوا جنب بعض، وفي نفس الـ loop ناخد أول نسخة بس من كل قيمة:
if (i > start && nums[i] === nums[i - 1]) continue. - ليه
i > startمشi > 0؟i === start= أول choice في الـ level ده، فمسموح دايمًا. الـnums[i - 1]وقتها مش أخ ليه، ده جوه الـ path من level فوق. وعشان نعمل[1, 2, 2]لازم ناخد الـ 2 التانية وإحنا نازلين.
- من غير الـ sort، الـ 2 في
[2, 1, 2]مش جنب بعض، والمقارنة بـnums[i - 1]مش هتشوفهم. - نفس Subsets بالظبط.
- السطر الوحيد الجديد. "مش أول واحد في الـ level، وأخويا اللي قبلي نفس القيمة واتجرّب خلاص" = فرع مكرر. بـ
i > 0هتطلع[[], [1], [1,2], [2]]:[1, 2, 2]و[2, 2]راحوا.
الـ nodes الحمرا اتفوّتت بسطر 8. بص على الـ label بتاعها: نفس label أخ ليها اتعمل قبلها:
التعقيد: sort O(n log n)، والـ worst case (كله مختلف) O(n · 2ⁿ) زي Subsets.
في كل اللي فات الـ choices جاية من نفس الـ array. طب لو كل level ليه list اختيارات مختلفة؟
مثال محلول 5: Letter Combinations of a Phone Number
عندك string أرقام من 2 لـ 9. كل رقم على كيبورد الموبايل القديم عليه حروف (2 = abc، 3 = def، … 7 = pqrs، 9 = wxyz). طلّع كل الكلمات اللي الأرقام دي ممكن تكتبها.
الجديد هنا إن الـ path string بيتبعت parameter، فمفيش unchoose خالص. وكمان كل level ليه list اختيارات خاصة بيه.
نفكّر فيها مع بعض
- الشجرة: عمقها = عدد الأرقام، وفي level
iالـ choices هي حروفdigits[i]. فمش محتاجينstartولاused. - الـ path كـ string:
path + chبيعمل string جديد، فكل call معاه نسخته، والـ "unchoose" بيحصل لوحده لما الـ call يرجع. - الـ edge case الخبيث:
""الإجابة[]مش[""]. من غير check، الـ base case هيتحقق عندi = 0ويسجّل string فاضي.
- الـ edge case قبل أي حاجة، وإلا الإجابة
[""]. - JS بتحوّل keys الـ object لـ strings، فـ
map['2']=map[2]، وده مناسب لأنdigits[i]string. - من غير copy: الـ string immutable، أي "تعديل" بيعمل string جديد.
- الـ
'7'ليها 4 حروف، فعدد الفروع مش دايمًا 3. - choose و explore في سطر واحد، ومفيش unchoose لأن
pathبتاعتنا ما اتغيّرتش. لو كان array كان لازمpushوpopوjoin('').
التعقيد: لحد 4ⁿ leaf، وكل واحدة string طوله n: O(n · 4ⁿ). والـ n لحد 4، يعني 256 كلمة بالكتير.
الـ path لحد دلوقتي كان list أو string. طب لو الـ path طريق ماشي فيه على grid، ومينفعش تعدّي على نفس الخانة مرتين؟
مثال محلول 6: Word Search (backtracking على grid)
عندك grid حروف وكلمة. هل تقدر تكتب الكلمة وإنت ماشي من خانة لخانة جنبها (فوق، تحت، يمين، شمال)، من غير ما تستخدم نفس الخانة مرتين؟
الجديد هنا إن الـ choose بيعلّم على الـ board نفسه ('#')، والـ unchoose بيرجّع الحرف. ومفيش res، المطلوب true أو false بس.
نفكّر فيها مع بعض
- منين نبدأ؟ أي خانة فيها أول حرف. نلف على كل الخانات ونجرّب منها.
- الشجرة: كل node =
(r, c, k): واقفين في الخانة دي وطابقنا لحد الحرفk. الـ choices: 4 جيران. - "مش نفس الخانة مرتين": نكتب
'#'مكان الحرف وإحنا نازلين، ونرجّعه وإحنا راجعين.'#'مش هتساوي أي حرف. - ليه لازم نرجّعها؟ الخانة ممكن تبقى مطلوبة في طريق تاني.
visitedعام ما بيتمسحش هيقفل طرق ممكن تنجح. - Pruning: أول ما الحرف ما يطابقش نرجع على طول، ولما نلاقي الكلمة الـ
||بتوقف باقي الاتجاهات.
- ليه ده أول سطر؟ بعد آخر حرف بننادي الجيران بـ
k = word.length، والجار ممكن يبقى برا الـ grid. لو الحدود قبله،[['a']]مع"a"بترجع false (جرّبتها). r >= rowsمشr > rows، لأن آخر صفrows - 1.- حرف غلط أو
'#'(في الطريق الحالي): early return، وده الـ pruning. - Choose: نحفظ الحرف ونحط
'#'. - الـ
||short-circuit: أول اتجاه يرجّع true الباقي ما بيتنفذش. - Unchoose حتى لو لقينا. لو اتشال السطر ده،
"ODOE"على الـ board ده بترجع false مع إنها موجودة: محاولة فاشلة سابت خانات عليها'#'والطريق الصح محتاجها.
الخانات اللي عليها # هي الطريق الحالي، والحمرا اترفضت (حرف غلط أو dead end):
التعقيد: لكل خانة من R × C بداية، الـ DFS بينزل لعمق L، وأول خطوة ليها 4 اتجاهات وبعدها 3 (اللي جيت منه عليه #): O(R · C · 3^L). والـ memory O(L).
visited بنفس الحجم وأعمل فيها set و unset".
آخر خطوة: لو الـ check إن الاختيار valid نفسه مكلّف؟ يعني محتاج تتأكد إن مفيش حاجة في الصف ولا العمود ولا القطر؟
مثال محلول 7 (اختياري، hard): N-Queens
حط n وزير (queen) على شطرنج n × n من غير ما أي اتنين يهاجموا بعض (نفس الصف أو العمود أو القطر). رجّع كل اللوحات الممكنة.
الجديد هنا إن الـ validity check بيتعمل في O(1) بتلات Sets بدل ما نلف على اللوحة.
نفكّر فيها مع بعض
- ملاحظة بتصغّر الشجرة جدًا: مينفعش اتنين في نفس الصف، ومعانا
nوزير وnصف. يبقى وزير واحد بالظبط في كل صف، والقرار في levelr: "في أنهي عمود؟". - خانة متهاجمة في O(1)؟ Set للأعمدة. وكل خانات القطر ↘ ليها نفس
r - c، وكل خانات القطر ↙ ليها نفسr + c. فتلات Sets. - Choose =
'Q'+ إضافة لـ 3 sets. Unchoose = نفس الأربع حاجات بالعكس.
| c = 0 | c = 1 | c = 2 | c = 3 | |
|---|---|---|---|---|
| r = 0 | r-c=0 · r+c=0 | -1 · 1 | -2 · 2 | -3 · 3 |
| r = 1 | 1 · 1 | 0 · 2 | -1 · 3 | -2 · 4 |
| r = 2 | 2 · 2 | 1 · 3 | 0 · 4 | -1 · 5 |
الخانات (0,0) و (1,1) و (2,2) كلها r - c = 0 (القطر ↘)، و (0,2) و (1,1) و (2,0) كلها r + c = 2 (القطر ↙).
- ليه
Array.from؟new Array(n).fill(new Array(n).fill('.'))بتحط نفس الصف (نفس الـ reference) في كل الخانات، فأي Q هتظهر في كل الصفوف. نفس مشكلةres.push(path). - كل Set بيرد على سؤال في O(1): العمود ده؟ القطر ↘ ده؟ القطر ↙ ده؟
r === n= وزير في كل صف من غير هجوم. الـmap(row => row.join(''))بتعمل copy كـ strings.- الـ pruning اللي بيخلّي الشجرة أصغر بكتير من
n^n. - Unchoose الأربع حاجات. لو نسيت
diag2مثلًا، خانات أمان هتبان متهاجمة وهتطلع حلول أقل.
الـ Q الخضرا اتحطّت، والخانات الرمادي متهاجمة (مقفولة)، والحمرا أعمدة جرّبناها في الصف الحالي ولقيناها متهاجمة:
التعقيد: الصف الأول n choice، والتاني بالكتير n - 1، وهكذا: O(n!) كـ upper bound، والـ pruning بيقلله كتير. والـ n لحد 9.
كل ده جميل، بس هيعدّي في الوقت؟ يلا نحسب بالأرقام.
الـ complexity: ليه الـ backtracking مقبول مع n صغيرة بس
في أي مسألة "طلّع كل الإجابات"، الـ output نفسه exponential: 2ⁿ subset أو n! ترتيب. ومفيش خوارزمية تطلّع 2ⁿ حاجة في أقل من 2ⁿ خطوة. عشان كده الـ constraints في المسائل دي صغيرة جدًا.
| المسألة | عدد الـ leaves | الوقت | الـ memory غير الـ output |
|---|---|---|---|
| Subsets | 2ⁿ | O(n · 2ⁿ) | O(n) |
| Permutations | n! | O(n · n!) | O(n) |
| Letter Combinations | 4ⁿ | O(n · 4ⁿ) | O(n) |
| Word Search | - | O(R · C · 3^L) | O(L) |
| N-Queens | - | O(n!) | O(n) |
افتكر جدول الـ constraints من فصل Big-O: الـ judge بيعمل حوالي 10⁸ عملية بسيطة في الثانية.
| n | 2ⁿ | n! | الحكم |
|---|---|---|---|
| 6 | 64 | 720 | أي حاجة تعدّي |
| 10 | 1,024 | 3,628,800 | permutations لسه تعدّي |
| 12 | 4,096 | 479,001,600 | permutations على الحافة، غالبًا TLE |
| 20 | 1,048,576 | 2.4 × 10¹⁸ | subsets تعدّي (× n ≈ 2 × 10⁷)، permutations مستحيل |
| 30 | 1.07 × 10⁹ | - | حتى الـ subsets مش هتلحق |
n ≤ 10: غالبًا permutations. n ≤ 20: غالبًا subsets (2ⁿ) أو bitmask. n ≥ 1000: مش backtracking. ولو المسألة شكلها "جرّب كل الاحتمالات" والـ n كبيرة، يبقى المطلوب عدد أو أحسن قيمة، ودي DP.
والـ pruning؟ غالبًا مش بيغيّر الـ worst case Big-O، بس بيفرق جدًا في الوقت الحقيقي. اسأل نفسك دايمًا: "إمتى أعرف بدري إن الفرع ده مش هيوصل؟".
قبل ما تحل لوحدك، دي الغلطات اللي غالبًا هتقع فيها.
غلطات مشهورة
كلها بتشتغل من غير أي error، وبتطلّع إجابة غلط.
1. res.push(path) بدل copy
لو الـ output طلع كله arrays فاضية أو شبه بعض، دي أول حاجة تشك فيها.
2. نسيت تعمل unchoose لحاجة غيّرتها
اعمل الـ unchoose مراية للـ choose: نفس السطور بالعكس. وفي الـ grid: أي '#' لازم يرجع حرفه.
3. backtrack(start + 1) بدل backtrack(i + 1)
الـ child يختار من بعد اللي لسه مختاره: i. وفي Combination Sum بيبقى i نفسه.
4. i > 0 بدل i > start في شيل التكرار
5. ترتيب الـ checks في الـ grid
شرط "خلصت" دايمًا قبل شروط "المكان ده غلط"، في أي DFS على grid.
6. نسيت الـ input الفاضي
Letter Combinations: "" → []، والـ template لوحده بيرجّع [""]. وSubsets بالعكس: [] → [[]]. اكتب الحالة دي في أول سطر.
يلا نختبر الكلام ده بأسئلة سريعة، وتمرين تفكّر فيه قبل ما تفتح الحل.
اختبر نفسك
كام subset للـ array [4, 5, 6, 7]؟
- 4
- 8
- 16
- 24
كل عنصر ليه قرارين: 2 × 2 × 2 × 2 = 16. والـ 24 = 4!، عدد الـ permutations.
في Permutations، ليه الـ loop بتبدأ من 0 مش من start؟
- عشان الكود يبقى أقصر
- عشان الترتيب فارق، وأي عنصر مش مستخدم ينفع في الخانة الجاية حتى لو الـ index بتاعه أصغر
- عشان نتجنب الـ stack overflow
- غلط، المفروض تبدأ من
start
الـ start بيمنع ترجع لعنصر قبلك، وده المطلوب في الـ subsets. في الـ permutations [2, 1] إجابة مطلوبة، و used هو اللي بيمنع التكرار.
في Combination Sum، ليه بننادي backtrack(i, ...) مش backtrack(i + 1, ...)؟
- عشان مسموح ناخد نفس الرقم تاني، بس مش مسموح نرجع لرقم قبله
- عشان نتجنب الـ break
- عشان الـ target يقل أسرع
- الاتنين نفس النتيجة
بـ i: [2, 2, 2] تطلع و [4, 2] لأ. بـ i + 1: كل رقم مرة بس، فتطلع [[2, 4]] بس.
في Subsets II على [1, 2, 2]: الـ path [1, 2] و start = 2 و i = 2، و nums[2] === nums[1]. نفوّت؟
- آه، لأن القيمة زي اللي قبلها
- لأ، لأن
i === start: أول choice في الـ level ده، والـ 2 اللي قبله جوه الـ path مش أخ ليه - آه، لأن
i > 0 - مش فارقة
لو فوّتنا، [1, 2, 2] عمرها ما هتطلع. الـ skip للإخوات في نفس الـ loop بعد أول واحد بس.
مسألة عايزة كل الـ permutations لـ array طولها 15. أحسن رد؟
- backtracking عادي، هيعدّي
- backtracking مع pruning
- 15! ≈ 1.3 × 10¹²، مستحيل. غالبًا فهمت المسألة غلط، أو المطلوب حاجة تانية زي العدد
- نستخدم memo
الـ output نفسه 10¹² array، حتى الطباعة مش هتلحق.
تمرين: فكّر قبل ما تفتح
عندك n و k. طلّع كل المجموعات اللي فيها k أرقام من 1 لـ n.
تلميح 1
دي Subsets بالظبط، بس بتسجّل في الـ nodes اللي طولها k بس، والأرقام من 1 لـ n بدل array.
تلميح 2
Pruning: لو الـ path ناقصه need رقم، ومفيش need رقم باقيين من i لـ n، الفرع مش هيوصل. يعني آخر i ممكن هو n - need + 1.
الحل
الـ <= عشان الأرقام من 1 لـ n والـ n نفسه مسموح. مثال: n = 4, k = 2 والـ path فاضي: need = 2، فآخر i = 3، لأن لو بدأت بـ 4 مفيش رقم بعده. جرّبتها: (4, 2) طلعت 6، و (5, 3) طلعت 10، و (1, 1) طلعت [[1]].
لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.
اتمرن على LeetCode بالترتيب
قبل أي كود، ارسم أول level أو اتنين من الشجرة على ورقة، واكتب: الـ path فيه إيه، وبنسجّل إمتى، والـ choices منين.
- Subsetsالمثال المحلول 1. اكتبه بالشكلين: ناخد/نسيب، والـ start.
- Sum of All Subset XOR Totalsنفس الشجرة، بس بتحسب حاجة على كل subset بدل ما تسجّلها.
- Combinationsالتمرين اللي فوق: تسجيل عند طول k، والـ pruning بـ need.
- Permutationsالـ used[] بدل الـ start.
- Combination Sumالـ remain كـ state، و backtrack(i)، و break.
- Subsets IIsort + i > start. أهم سطر في الفصل.
- Combination Sum IICombination Sum + Subsets II: i + 1 والـ skip.
- Permutations IIشيل التكرار في الـ permutations: الشرط على used[i - 1].
- Combination Sum IIIbase case بشرطين: الطول k والمجموع n.
- Letter Combinations of a Phone Numberpath كـ string، ومفيش unchoose.
- Generate Parenthesesالـ pruning هو المسألة كلها: ")" بس لو المفتوح أكتر.
- Word Searchbacktracking على grid: علّم وارجع.
- Palindrome Partitioningالـ choice هنا "أقطع فين"، مش "آخد أنهي عنصر".
- N-Queensاختياري: صف لكل level، وتلات sets للهجوم.
وفي الآخر، الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.
الخلاصة
| السؤال | الإجابة |
|---|---|
| الترتيب فارق؟ | لأ: start. آه: loop من 0 و used[]. |
| مسموح أعيد العنصر؟ | لأ: backtrack(i + 1). آه: backtrack(i). |
| الـ input فيه تكرار؟ | sort + i > start && nums[i] === nums[i - 1]. |
| بنسجّل إمتى؟ | Subsets: كل node. Combinations: الطول أو المجموع. Permutations: path.length === n. |
path ولا [...path]؟ | دايمًا copy لو array. لو string مش محتاج. |
| الـ unchoose ناقص حاجة؟ | اعمله مراية للـ choose: كل سطر غيّر حاجة يقابله سطر يرجّعها. |
| هيعدّي؟ | احسب الـ leaves: 2ⁿ لحد n ≈ 20، و n! لحد n ≈ 10. |
الفصل الجاي: بص على Combination Sum تاني. لو المسألة قالت "كام مجموعة؟" أو "أقل عدد أرقام يوصّلك للـ target؟"، هتلاقي إن نفس الـ state (start, remain) بيتحسب مرات كتير في فروع مختلفة. لو افتكرنا نتيجة كل state أول ما نحسبها، الشجرة الـ exponential تبقى عدد states محدود. ده الـ Dynamic Programming: backtracking + memory.