Backtracking with Choices, Constraints, and Undo
آمادگی مصاحبهٔ الگوریتمی با Python
- In 75 minutes, recognize requests to enumerate valid constructions and distinguish path-specific state from globally visited graph vertices.
- Define a recursive state, available choices, stopping condition, and choose-explore-undo sequence.
- Independently identify which partial parenthesis strings can never become valid before seeing a pruning rule.
- Develop Generate Parentheses from generating every length-2n candidate and filtering to a Python backtracking solution that extends only valid prefixes.
- Prove soundness through prefix balance and completeness through considering every legal next choice; explain why pruning cannot remove a valid completion.
- Analyze the search tree, O(n) working depth, and output-sensitive construction cost; distinguish a safe exponential bound from the number of valid outputs.
- Test n equal to zero, one, and two; diagnose mutable-path aliasing, missing undo, and claims that pruning makes all enumeration polynomial.
- Reject enumeration when input size and output requirements call for counting or optimization through reusable subproblems instead.
درخت انتخاب و شاخههای بیآینده
```svg
<svg viewBox="0 0 800 510" xmlns="http://www.w3.org/2000/svg"><rect x="180" y="15" width="440" height="80" rx="14" class="tm-soft"/><text x="400" y="47" text-anchor="middle" class="tm-text" font-size="23">Generate Parentheses</text><text x="400" y="77" text-anchor="middle" direction="rtl" class="tm-text2" font-size="18">با n جفت، همهی رشتههای درست</text><text x="210" y="130" text-anchor="middle" class="tm-text-accent" font-size="18">backtracking / DFS</text><path d="M210 180 L110 225 M210 180 L310 225" class="tm-line"/><rect x="155" y="145" width="110" height="40" rx="10" class="tm-surface"/><text x="210" y="171" text-anchor="middle" class="tm-text" font-size="17" direction="rtl">رشتهی خالی</text><rect x="75" y="225" width="70" height="45" rx="10" class="tm-soft"/><text x="110" y="255" text-anchor="middle" direction="ltr" class="tm-text" font-size="27">(</text><rect x="275" y="225" width="70" height="45" rx="10" class="tm-soft"/><text x="310" y="255" text-anchor="middle" direction="ltr" class="tm-text" font-size="27">)</text><text x="210" y="302" text-anchor="middle" direction="rtl" class="tm-muted" font-size="17">هر شاخه: یک انتخاب</text><rect x="440" y="112" width="330" height="210" rx="14" class="tm-surface"/><text x="605" y="143" text-anchor="middle" class="tm-text" font-size="20">Brute Force</text><text x="605" y="177" text-anchor="middle" direction="rtl" class="tm-text2" font-size="18">n = 2؛ 16 نامزد طول 4</text><text x="605" y="211" text-anchor="middle" direction="rtl" class="tm-muted" font-size="16">ابتدا ساختن، سپس بررسی اعتبار</text><text x="605" y="247" text-anchor="middle" class="tm-text2" font-size="17">balance: ( +1 ) −1</text><text x="605" y="281" text-anchor="middle" direction="rtl" class="tm-text2" font-size="16">هرگز منفی نشود؛ در پایان صفر</text><text x="605" y="308" text-anchor="middle" direction="ltr" class="tm-text-green" font-family="monospace" font-size="22">(()) ()()</text><text x="400" y="357" text-anchor="middle" direction="rtl" class="tm-text" font-size="20">کدام شروع را میشود کامل کرد؟</text><rect x="30" y="380" width="230" height="110" rx="12" class="tm-soft"/><rect x="285" y="380" width="230" height="110" rx="12" class="tm-soft"/><rect x="540" y="380" width="230" height="110" rx="12" class="tm-soft"/><text x="145" y="416" text-anchor="middle" direction="ltr" class="tm-text" font-family="monospace" font-size="28">)</text><text x="400" y="416" text-anchor="middle" direction="ltr" class="tm-text" font-family="monospace" font-size="28">(((</text><text x="655" y="416" text-anchor="middle" direction="ltr" class="tm-text" font-family="monospace" font-size="28">()</text><path d="M116 389 L174 424 M174 389 L116 424 M355 389 L445 424 M445 389 L355 424" class="tm-line-accent"/><text x="145" y="453" text-anchor="middle" direction="rtl" class="tm-text-accent" font-size="17">بستهی بیجفت</text><text x="145" y="478" text-anchor="middle" direction="rtl" class="tm-muted" font-size="15">با ادامه دادن درست نمیشود</text><text x="400" y="453" text-anchor="middle" direction="rtl" class="tm-text-accent" font-size="17">بازِ بیش از تعداد جفتها</text><text x="400" y="478" text-anchor="middle" direction="rtl" class="tm-muted" font-size="15">با ادامه دادن درست نمیشود</text><text x="655" y="451" text-anchor="middle" direction="ltr" class="tm-text-green" font-family="monospace" font-size="22">() → ()()</text><text x="655" y="478" text-anchor="middle" direction="rtl" class="tm-text-green" font-size="17">قابلتکمیل</text></svg>
```
پیادهسازی چرخهی choose، explore و undo
**Generate Parentheses در Python**
قانون هر فراخوانی: \(0 \leq closed \leq opened \leq n\)
```python
def generateparentheses(n):
result = []
path = []
def dfs(opened, closed):
if closed == n:
result.append(''.join(path))
return
if opened < n:
path.append('(') # choose
dfs(opened + 1, closed) # explore
path.pop() # undo
if closed < opened:
path.append(')') # choose
dfs(opened, closed + 1) # explore
path.pop() # undo
dfs(0, 0)
return result
```
دو `if` مستقل؛ نه `if` و `elif`.
`path` مشترک است و به `undo` نیاز دارد؛ شمارندهها با آرگومانهای تازه منتقل میشوند.
ردگیری مسیر، undo و خروجی مستقل
| مرحله | وضعیت: \((path, open, close)\) | خروجی / نکته |
| --- | --- | --- |
| شاخهی اول؛ \(n=2\) | \(\begin{gathered}(\texttt{""},0,0)\to(\texttt{"("},1,0)\to(\texttt{"(("},2,0)\\\to(\texttt{"(()"},2,1)\to(\texttt{"(())"},2,2)\end{gathered}\) | ذخیره: \(\texttt{"(())"}\) |
| برگشت با pop | \(\begin{gathered}(\texttt{"(())"},2,2)\to(\texttt{"(()"},2,1)\\\to(\texttt{"(("},2,0)\to(\texttt{"("},1,0)\end{gathered}\) | حذف بسته، بسته، باز |
| شاخهی دوم | \(\begin{gathered}(\texttt{"("},1,0)\to(\texttt{"()"},1,1)\\\to(\texttt{"()("},2,1)\to(\texttt{"()()"},2,2)\end{gathered}\) | ذخیره: \(\texttt{"()()"}\) |
| برگشت نهایی | \(\begin{gathered}(\texttt{"()()"},2,2)\to(\texttt{"()("},2,1)\\\to(\texttt{"()"},1,1)\to(\texttt{"("},1,0)\to(\texttt{""},0,0)\end{gathered}\) | \(\texttt{result}=[\texttt{"(())"},\texttt{"()()"}]\) |
| خطا: حذف pop | path: علامتِ اضافه باقی میماند؛ شمارندهها: مقدار فراخواننده | append ← فراخوانی ← pop؛ هر append یک pop دارد. |
| خطا: ذخیرهی خود path | ورودیهای result ← همان فهرست path | undo خروجیها را هم تغییر میدهد؛ حتی تا خالیشدن. |
| ذخیرهی مستقل | رشته: join؛ فهرستِ علامتها: copy | خروجی با undo تغییر نمیکند. |
| تستهای کوچک | \(\begin{aligned}n=0&\Rightarrow[\texttt{""}]\\n=1&\Rightarrow[\texttt{"()"}]\\n=2&\Rightarrow[\texttt{"(())"},\texttt{"()()"}]\end{aligned}\) | یک عضوِ خالی؛ نه \([]\) |
اثبات درستی و مرزهای pruning
**soundness: هر خروجی معتبر است**
قانون همهٔ پیشوندها: \(0 \le closed \le opened \le n\)
انتخاب باز: \(opened<n\)؛ انتخاب بسته: \(closed<opened\).
پایان: \(closed=n \Rightarrow opened=n \Rightarrow |path|=2n\).
**completeness: هیچ جوابی جا نمیماند**
علامتهای هر جواب معتبر را از ابتدا دنبال کن:
بازِ بعدی ⟵ شرط \(opened<n\) برقرار است.
بستهٔ بعدی ⟵ شرط \(closed<opened\) برقرار است.
پس تمام مسیر وجود دارد؛ هر رشته هم توالی انتخاب یکتایی دارد.
**pruning: پیشوند خراب تعمیر نمیشود**
بازِ بیش از سهم یا بستهٔ بیجفت با افزودن علامت به انتها اصلاح نمیشود.
نمونه: \(\texttt{)(}\) شمارندههای برابر دارد، اما پیشوند \(\texttt{)}\) همچنان نامعتبر است.
**شمارندهٔ یکسان، خروجی متفاوت**
برای \(n=3\)، هر دو مسیر شمارندههای \((opened,closed)=(2,1)\) دارند:
\(\texttt{(()}+\texttt{())}\longrightarrow\texttt{(()())}\)
\(\texttt{()(}+\texttt{())}\longrightarrow\texttt{()(())}\)
ثبت سراسری جفت شمارندهها در visited یکی از جوابها را حذف میکند. درخت دور ندارد: طول مسیر در هر قدم بیشتر میشود.
هزینه به حجم خروجی وابسته است
\(n\): تعداد جفتها؛ \(K\): تعداد جوابهای معتبر همین ورودی
**درخت کامل Brute Force**
\[ d=2n,\qquad L\le 2^{2n}=4^n \]
در هر قدم حداکثر دو انتخاب داریم.
**بررسی رشتههای کامل**
\[ T_{\mathrm{brute}}(n)=O(n\cdot 4^n) \]
این کران برای نسخهٔ pruning هم امن است؛ تعداد دقیق جوابها نیست.
**حداقل هزینهٔ نوشتن خروجی**
\[ |\mathrm{answer}|=2n\quad\Longrightarrow\quad T_{\mathrm{output}}=\Theta(nK)\qquad(n>0) \]
هر جواب باید به صورت رشتهای مستقل ساخته شود.
**کران تعداد گرههای جستوجو**
\[ N\le 1+2nK=O(nK)\qquad(n>0) \]
هر پیشوند مجاز قابلتکمیل است؛ هر گره روی مسیر حداقل یک جواب قرار دارد.
**زمان کل با append و pop ثابت**
\[ T(n)=\Theta(nK)\quad(n>0),\qquad T(0)=\Theta(1) \]
کران بالای پیمایش و کران پایین نوشتن خروجی با هم منطبقاند.
**فضای کاری، جدا از جوابها**
\[ |\mathrm{path}|\le 2n,\quad d\le 2n\quad\Longrightarrow\quad S_{\mathrm{work}}=O(n)\qquad(n>0) \]
path و پشتهٔ فراخوانی
**فضای نگهداری خروجی**
\[ S_{\mathrm{output}}=\Theta(nK)\qquad(n>0) \]
تعداد رشتهها ضربدر طول هر رشته
**برای تعداد جفتِ زوج**
\[ m=\frac{n}{2},\qquad B_i\in\bigl\{\texttt{(())},\texttt{()()}\bigr\},\quad 1\le i\le m \]
هر بلوک دو جفتی، مستقل یکی از دو جواب معتبر را انتخاب میکند.
**pruning الزاماً چندجملهای نیست**
\[ K\ge 2^m=2^{n/2}\quad\Longrightarrow\quad T(n)=\Omega\!\left(n\,2^{n/2}\right) \]
ترکیب بلوکها معتبر و متفاوت است. اگر فقط تعداد یا بهترین مقدار لازم است، ساخت تکتک جوابها ممکن است انتخاب بدی باشد.
Back to course