Backtrackingdecision tree · choose → explore → unchoose · pruning

في فصول الـ recursion والـ trees شفت دالة بتنادي نفسها وبترسم شجرة calls. هنا هنستخدم الشجرة دي عشان نجرّب كل الاحتمالات بنظام: تختار، تكمّل، ولما تخلص ترجع في اختيارك وتجرّب اللي بعده. ده الـ backtracking.

قبله: Recursion و Binary Trees بيمهّد لـ: Dynamic Programming 1

هتطلع من الفصل ده وإنت عارف

  • تشوف أي مسألة "كل الاحتمالات" على إنها 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.

تذكير بالـ recursion (هنعتمد عليه طول الفصل)
  • كل call ليه نسخته من المتغيرات. لو go(0) نادت go(1)، الـ i جوه go(1) = 1، والـ i بتاع go(0) لسه 0 ومستني.
  • لما الـ call يخلص، بيرجع لنفس السطر اللي اتنادى منه ويكمّل اللي بعده. ده اللي هيخلّينا "نرجع لورا" ونجرّب اختيار تاني.
  • الـ call stack فيه الـ calls اللي لسه ما خلصتش. اللي فوق شغال، والباقي waiting. هتشوفه في الـ animations.
تشبيه إنت ماشي في متاهة ومعاك طباشير. عند كل مفترق بتختار طريق وبتعلّم على الحيطة. لو الطريق قفل في وشك، بترجع لآخر مفترق، وتمسح العلامة اللي عملتها، وتجرّب الطريق اللي بعده. الرجوع ده هو الـ backtrack، ومسح العلامة هو الـ unchoose.

الـ decision tree

ارسم القرارات كشجرة: الـ root = "لسه ما قررتش حاجة". من كل node فرعين: الشمال = سبت العنصر، اليمين = أخدته. كل node هي partial choice: قررت في أول كام عنصر والباقي لسه. ولما توصل لعمق n تبقى leaf، يعني subset كاملة.

  1. path هو array واحدة بس بتمثّل الـ node اللي إحنا واقفين عندها. كل الـ calls بتشاركها، وده سبب كل التفاصيل اللي جاية.
  2. go(i) معناها: "قررت في nums[0..i-1]، ودلوقتي هقرر في nums[i]". يعني i = عمق الـ node.
  3. ليه nums.length مش nums.length - 1؟ لما i = 2 لسه ما قررناش في الـ 3. جرّبتها بـ - 1: بتطلع 4 subsets بس [[], [2], [1], [1, 2]]، ومفيش ولا واحدة فيها 3.
  4. بنسجّل copy من الـ path، لأنه هيتغيّر بعد كده. التفاصيل في قسم الـ template.
  5. ده الـ base case. من غيره go(4) و go(5)… لحد Maximum call stack size exceeded.
  6. Branch 1: نسيب nums[i]. الـ path ما بيتغيّرش.
  7. Branch 2: ناخده وننزل.
  8. أهم سطر. الـ invariant: كل call بيرجّع الـ path زي ما استلمه، لأن اللي نادانا مستني يلاقيه زي ما ساب.

اتفرّج على الشجرة وهي بتتبني. الأصفر = الـ node الحالية، والأوراق الخضرا اتسجّلت، والرقم تحتها ترتيب التسجيل:

15 node، منهم 8 leaves = 8 subsets. وترتيب الـ calls هو نفسه DFS على الشجرة: بننزل للآخر، ونرجع خطوة، ونجرّب الفرع التاني.

الفكرة اللي لازم تفضل معاك أي backtracking هو DFS على decision tree. الشجرة مش موجودة في الـ memory، الـ recursion بترسمها وهي ماشية: كل node = partial choice، كل edge = قرار، وكل leaf (أو node بتحقق الشرط) = إجابة.

طب إزاي تعرف من كلام المسألة إنها backtracking أصلًا؟

إزاي تعرفه من المسألة

أوضح signal كلمة "كل": كل الـ subsets، كل الترتيبات، كل الطرق. والتانية إن الـ constraints صغيرة جدًا (n ≤ 10 أو n ≤ 15). المسألة بتقولك من غير ما تقول: "جرّب كله".

لما تشوف: all subsets / power setall permutationsall combinationsreturn all possible generate all validn ≤ 10 أو n ≤ 15choose kpartition into word search in gridN-Queens / Sudoku
ومش هو غالبًا لو: count the number of ways (من غير ما تطلّعهم)minimum / maximumn up to 10⁵

لو المطلوب عدد الطرق بس، أو أحسن قيمة، فغالبًا فيه حل أسرع بكتير بالـ Dynamic Programming. الـ backtracking بيطلّع الإجابات نفسها واحدة واحدة، فلو عددها مليارات مش هيلحق.

النوعبنسجّل إمتىالـ loop بتبدأ منينالـ call الجايمسائل
Subsetsفي كل nodestartbacktrack(i + 1)78
Combinationsلما الطول k أو المجموع targetstarti + 1، أو i لو التكرار مسموح77، 39
Permutationsلما path.length === n0 مع 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

قبل ما تكتب أي سطر، جاوب على تلات أسئلة:

  1. الـ path فيه إيه؟ الـ partial choice اللي بتبنيه: عناصر، حروف، أماكن queens.
  2. إمتى الـ path يبقى إجابة كاملة؟ ده الـ base case: طوله n، المجموع صفر، وصلت لآخر صف.
  3. إيه الـ choices المتاحة، وإيه الممنوع؟ دي الـ loop وشروطها.
  1. ليه path واحدة مشتركة؟ لو كل call عمل array جديدة، ده copy بـ O(n) في كل node. مع array واحدة الـ push والـ pop الاتنين O(1). الـ trade-off: لازم ترجّع كل حاجة بإيدك (سطر 13).
  2. state = اللي محتاجه عشان تعرف إنت فين في الشجرة: start، أو remain، أو رقم الصف، أو (r, c, k).
  3. الـ base case، بيختلف حسب المسألة: path.length === n، أو remain === 0، أو مفيش شرط خالص زي الـ subsets.
  4. Copy. [...path] بتعمل array جديدة بالعناصر اللي دلوقتي. تحت هتشوف بالـ animation إيه اللي بيحصل من غيرها.
  5. Early return: الإجابة كاملة، مفيش داعي ننزل. في Letter Combinations لو نسيته هتقرا digits[i] بعد آخر الـ string وتضرب TypeError.
  6. Pruning: لو عارف من دلوقتي إن الـ choice ده مش هيوصل، ما تنزلش فيه. ده بيشيل subtree كامل مرة واحدة.
  7. Choose وبعدين explore: لما الـ call ده يرجع، يبقى جرّبنا كل الإجابات اللي بتبدأ بالـ path ده.
  8. 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

Subsets

mediumLeetCode 78

عندك array أرقامها كلها مختلفة. رجّع كل المجموعات الجزئية (الـ power set). نفس المجموعة ما تتكررش، والترتيب مش مهم.

Input: nums = [1, 2, 3] Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] Input: nums = [0] Output: [[], [0]]

نفكّر فيها مع بعض

  1. افهم المطلوب: subset مالهاش ترتيب: [1, 2] هي [2, 1]، فتطلع مرة واحدة.
  2. Brute force: شجرة "ناخد ولا نسيب" = O(n · 2ⁿ)، ومفيش أحسن منها لأن الـ output نفسه 2ⁿ subset. السؤال هنا "إزاي أكتب template أقدر أعيد استخدامه".
  3. الـ key insight: بدل "ناخد ولا نسيب"، نسأل في كل node: "العنصر الجاي إيه؟"، بشرط إنه ييجي بعد آخر عنصر أخدناه. كده كل subset بتطلع بترتيب الـ indices: [1, 2] آه، و [2, 1] عمرها.
  4. الـ start index: أول index مسموح نختار منه. الـ root بيبدأ بـ 0، ولو اخترت nums[i] الـ child بياخد i + 1.
  5. بنسجّل إمتى؟ في الشكل ده كل node subset صح، فبنسجّل أول ما ندخل أي call. والـ edge case: array فاضية الإجابة [[]].
  1. start = أول index مسموح في الـ node دي، وهو اللي بيمنع التكرار.
  2. مفيش if. كل node subset، فبنسجّل على طول. والـ base case مستخبّي: لما start === nums.length الـ loop مش بتلف والدالة بترجع لوحدها.
  3. ليه i = start مش 0؟ من 0 هتختار نفس العنصر تاني: [1, 1, 1, …] لحد stack overflow. و i < nums.length مش <=، وإلا هتعمل push(undefined).
  4. i + 1 مش start + 1، أشهر غلطة هنا. الـ child يبدأ بعد اللي لسه مختاره. جرّبت start + 1: بتطلع 16 array بدل 8، فيهم [2, 2] و [3, 2].
  5. Unchoose، عشان الـ i الجاية تبدأ من نفس الـ path.

الخانات الباهتة في nums هي اللي قبل start (ممنوعة في الـ call ده)، والرقم على كل edge هو العنصر اللي اتضاف:

Inputالمتوقعليه الحالة دي مهمة
[][[]]الـ loop مش بتلف، بس سطر 5 بيسجّل [].
[5][[], [5]]أبسط شجرة: root و child واحد.
10 عناصر1024 subset2¹⁰، أقصى n في المسألة.

التعقيد: 2ⁿ node، وكل node بتعمل copy لحد n: O(n · 2ⁿ) وقت. والـ memory غير الـ output: O(n) للـ path والـ stack.

هنا الترتيب ما كانش فارق. طب لو [1, 2] و [2, 1] إجابتين مختلفتين؟

مثال محلول 2: Permutations

Permutations

mediumLeetCode 46

عندك array أرقامها مختلفة. رجّع كل الترتيبات الممكنة ليها.

Input: nums = [1, 2, 3] Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] Input: nums = [0, 1] Output: [[0,1], [1,0]]

الجديد هنا إن الترتيب فارق، فالـ start index مش هينفع، ومحتاجين طريقة تانية نعرف بيها مين اتاخد.

نفكّر فيها مع بعض

  1. ليه الـ start مش هينفع؟ الـ start بيقول "من اللي بعدي بس". لو اخترت 3 الأول مش هتقدر ترجع للـ 1، فـ [3, 1, 2] عمرها ما هتطلع. جرّبتها: بتطلّع [[1, 2, 3]] بس.
  2. الـ key insight: في كل خانة، أي عنصر لسه ما اتاخدش ينفع. فنحتفظ بـ used[i] = true لو nums[i] في الـ path دلوقتي.
  3. ليه مش path.includes(x)؟ ده O(n) في كل check بدل O(1)، وبيبوظ مع الأرقام المتكررة لأن used شغالة بالـ index مش بالقيمة.
  4. بنسجّل لما path.length === nums.length. والـ unchoose بقى حاجتين، لأن الـ choose غيّر حاجتين.
  1. fill(false) مهمة: new Array(n) لوحدها بتعمل empty slots قيمتها undefined. هتشتغل لأن undefined falsy، بس الـ fill أوضح.
  2. مفيش parameter: الـ state كله في path و used، والعمق هو path.length.
  3. من 0 كل مرة، لأن أي عنصر مش مستخدم ينفع في الخانة الجاية، حتى لو الـ index بتاعه أصغر.
  4. اللي في الـ path ما يتكررش في نفس الـ permutation.
  5. 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).

في الانترفيو غالبًا هيسألك: "ولو فيه أرقام متكررة؟" (Permutations II، 47). الحل: sort، وفوّت nums[i] لو زي nums[i - 1] و used[i - 1] بـ false. يعني النسخ المتساوية تتاخد دايمًا بالترتيب.

لحد دلوقتي كل عنصر بيتاخد مرة واحدة بالكتير. طب لو مسموح تعيده، ومحتاج توقف عند مجموع معيّن؟

مثال محلول 3: Combination Sum

Combination Sum

mediumLeetCode 39

عندك أرقام موجبة مختلفة candidates و target. طلّع كل المجموعات اللي مجموعها target، ومسموح تستخدم نفس الرقم أكتر من مرة. نفس الأرقام بترتيب مختلف = نفس المجموعة.

Input: candidates = [2, 3, 4], target = 6 Output: [[2,2,2], [2,4], [3,3]] Input: candidates = [5], target = 3 Output: []

الجديد هنا حاجتين صغيرين: الـ call بياخد i مش i + 1 عشان التكرار، وأول pruning حقيقي بيقطع فروع كاملة.

نفكّر فيها مع بعض

  1. combination ولا permutation؟ [2, 4] = [4, 2]، يعني الترتيب مش فارق: template الـ start.
  2. التكرار مسموح: بدل backtrack(i + 1) ننادي backtrack(i): "خد نفس العنصر تاني لو عايز، بس عمرك ما ترجع لعنصر قبله". ده بيسمح بـ [2, 2, 2] ويمنع [4, 2].
  3. الـ state: (start, remain)، و remain = الباقي للـ target. بنسجّل لما remain === 0.
  4. Pruning: لو رتّبنا، وقابلنا رقم أكبر من remain، يبقى هو وكل اللي بعده أكبر. break مش continue.
  5. ليه الـ recursion بتخلص؟ لأن كل الأرقام موجبة، فـ remain بيقل في كل level. لو كان فيه صفر، backtrack(i) هيلف للأبد.
  1. الـ sort عشان الـ break في سطر 11. والـ comparator لازم، من غيره JS بترتّب الأرقام كـ strings ([10, 9, 2] تبقى [10, 2, 9])، والـ break هيقطع فروع فيها إجابات.
  2. وصلنا للـ target بالظبط. مش محتاجين حالة remain < 0، لأن سطر 11 بيمنعنا ننزل في أي فرع هيعدّي.
  3. ليه break؟ الـ array مترتبة، فكل اللي بعد candidates[i] أكبر منه. continue هيدّي نفس النتيجة، بس هيلف على عناصر عارفين إنها مش هتنفع.
  4. بـ i مش i + 1: ده الفرق الوحيد عن الـ subsets. بـ i + 1 هتطلع [[2, 4]] بس.
  5. بنعمل 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 II

mediumLeetCode 90

زي Subsets، بس الـ array ممكن يكون فيها أرقام متكررة. رجّع كل الـ subsets من غير ما أي واحدة تتكرر.

Input: nums = [2, 1, 2] Output: [[], [1], [1,2], [1,2,2], [2], [2,2]] Input: nums = [0] Output: [[], [0]]

الجديد هنا سطر واحد بيمنع الإجابات المكررة، وهتستخدمه في أي مسألة input فيها تكرار.

نفكّر فيها مع بعض

  1. Subsets زي ما هو؟ على [1, 2, 2] هيطلّع [1, 2] مرتين و [2] مرتين: 8 بدل 6.
  2. التكرار بييجي منين؟ node واحدة اختارت مرة الـ 2 اللي عند index 1، ومرة اللي عند index 2. دول إخوات في نفس الـ level، ونفس القيمة، فالـ subtrees اللي تحتهم متطابقة.
  3. الحل: sort عشان المتساويين يبقوا جنب بعض، وفي نفس الـ loop ناخد أول نسخة بس من كل قيمة: if (i > start && nums[i] === nums[i - 1]) continue.
  4. ليه i > start مش i > 0؟ i === start = أول choice في الـ level ده، فمسموح دايمًا. الـ nums[i - 1] وقتها مش أخ ليه، ده جوه الـ path من level فوق. وعشان نعمل [1, 2, 2] لازم ناخد الـ 2 التانية وإحنا نازلين.
  1. من غير الـ sort، الـ 2 في [2, 1, 2] مش جنب بعض، والمقارنة بـ nums[i - 1] مش هتشوفهم.
  2. نفس Subsets بالظبط.
  3. السطر الوحيد الجديد. "مش أول واحد في الـ 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.

القاعدة اللي هتستخدمها كتير Input فيه تكرار + "ما تطلّعش إجابات مكررة" = sort + skip الأخ اللي زي اللي قبله في نفس الـ level. نفس السطر في Subsets II و Combination Sum II و 3Sum.

في كل اللي فات الـ choices جاية من نفس الـ array. طب لو كل level ليه list اختيارات مختلفة؟

مثال محلول 5: Letter Combinations of a Phone Number

Letter Combinations of a Phone Number

mediumLeetCode 17

عندك string أرقام من 2 لـ 9. كل رقم على كيبورد الموبايل القديم عليه حروف (2 = abc، 3 = def، … 7 = pqrs، 9 = wxyz). طلّع كل الكلمات اللي الأرقام دي ممكن تكتبها.

Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"] Input: digits = "" Output: []

الجديد هنا إن الـ path string بيتبعت parameter، فمفيش unchoose خالص. وكمان كل level ليه list اختيارات خاصة بيه.

نفكّر فيها مع بعض

  1. الشجرة: عمقها = عدد الأرقام، وفي level i الـ choices هي حروف digits[i]. فمش محتاجين start ولا used.
  2. الـ path كـ string: path + ch بيعمل string جديد، فكل call معاه نسخته، والـ "unchoose" بيحصل لوحده لما الـ call يرجع.
  3. الـ edge case الخبيث: "" الإجابة [] مش [""]. من غير check، الـ base case هيتحقق عند i = 0 ويسجّل string فاضي.
  1. الـ edge case قبل أي حاجة، وإلا الإجابة [""].
  2. JS بتحوّل keys الـ object لـ strings، فـ map['2'] = map[2]، وده مناسب لأن digits[i] string.
  3. من غير copy: الـ string immutable، أي "تعديل" بيعمل string جديد.
  4. الـ '7' ليها 4 حروف، فعدد الفروع مش دايمًا 3.
  5. choose و explore في سطر واحد، ومفيش unchoose لأن path بتاعتنا ما اتغيّرتش. لو كان array كان لازم push و pop و join('').

التعقيد: لحد 4ⁿ leaf، وكل واحدة string طوله n: O(n · 4ⁿ). والـ n لحد 4، يعني 256 كلمة بالكتير.

الـ path لحد دلوقتي كان list أو string. طب لو الـ path طريق ماشي فيه على grid، ومينفعش تعدّي على نفس الخانة مرتين؟

مثال محلول 7 (اختياري، hard): N-Queens

N-Queens

hardLeetCode 51

حط n وزير (queen) على شطرنج n × n من غير ما أي اتنين يهاجموا بعض (نفس الصف أو العمود أو القطر). رجّع كل اللوحات الممكنة.

Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]] Input: n = 1 Output: [["Q"]]

الجديد هنا إن الـ validity check بيتعمل في O(1) بتلات Sets بدل ما نلف على اللوحة.

نفكّر فيها مع بعض

  1. ملاحظة بتصغّر الشجرة جدًا: مينفعش اتنين في نفس الصف، ومعانا n وزير و n صف. يبقى وزير واحد بالظبط في كل صف، والقرار في level r: "في أنهي عمود؟".
  2. خانة متهاجمة في O(1)؟ Set للأعمدة. وكل خانات القطر ↘ ليها نفس r - c، وكل خانات القطر ↙ ليها نفس r + c. فتلات Sets.
  3. Choose = 'Q' + إضافة لـ 3 sets. Unchoose = نفس الأربع حاجات بالعكس.
c = 0c = 1c = 2c = 3
r = 0r-c=0 · r+c=0-1 · 1-2 · 2-3 · 3
r = 11 · 10 · 2-1 · 3-2 · 4
r = 22 · 21 · 30 · 4-1 · 5

الخانات (0,0) و (1,1) و (2,2) كلها r - c = 0 (القطر ↘)، و (0,2) و (1,1) و (2,0) كلها r + c = 2 (القطر ↙).

  1. ليه Array.from؟ new Array(n).fill(new Array(n).fill('.')) بتحط نفس الصف (نفس الـ reference) في كل الخانات، فأي Q هتظهر في كل الصفوف. نفس مشكلة res.push(path).
  2. كل Set بيرد على سؤال في O(1): العمود ده؟ القطر ↘ ده؟ القطر ↙ ده؟
  3. r === n = وزير في كل صف من غير هجوم. الـ map(row => row.join('')) بتعمل copy كـ strings.
  4. الـ pruning اللي بيخلّي الشجرة أصغر بكتير من n^n.
  5. 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
Subsets2ⁿO(n · 2ⁿ)O(n)
Permutationsn!O(n · n!)O(n)
Letter Combinations4ⁿ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⁸ عملية بسيطة في الثانية.

n2ⁿn!الحكم
664720أي حاجة تعدّي
101,0243,628,800permutations لسه تعدّي
124,096479,001,600permutations على الحافة، غالبًا TLE
201,048,5762.4 × 10¹⁸subsets تعدّي (× n ≈ 2 × 10⁷)، permutations مستحيل
301.07 × 10⁹-حتى الـ subsets مش هتلحق
اقرا الـ constraints كأنها hint 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، حتى الطباعة مش هتلحق.

تمرين: فكّر قبل ما تفتح

Combinations

mediumLeetCode 77

عندك n و k. طلّع كل المجموعات اللي فيها k أرقام من 1 لـ n.

n = 4, k = 2 → [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
تلميح 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 منين.

وفي الآخر، الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.

الخلاصة

في جملة واحدة Backtracking = DFS على decision tree: اختار، انزل، ارجع في اختيارك، وسجّل copy من الـ path لما يبقى إجابة، واقطع أي فرع عارف بدري إنه مش هيوصل.
السؤالالإجابة
الترتيب فارق؟لأ: 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.