# Recursion and Backtracking — Named Patterns

সাতটা pattern, এমনভাবে সাজানো যেন প্রতিটা আগেরটার উপর দাঁড়ায়। প্রতিটা pattern-এর জন্য: trigger words, core idea, thinking tweak, একটা ছোট worked example, কী থেকে inherit করে, আর practice problem।

## Pattern 1: Decrease-and-conquer

- **Trigger words:** "n in terms of n-1", "একটা element process করো তারপর বাকিটা", linear structure (string, list, countdown)।
- **Core idea:** একটা টুকরো খুলে নাও, বাকিটার উপর recurse করো, জোড়া লাগাও।
- **Inherits from:** loops — decrease-by-one যেকোনো recursion-এর একটা loop-যমজ আছে; এই pattern সেই recursive ভাষাটা শেখায়, যেটা loop-এ আর না কুলালে লাগবে।
- **Thinking tweak:** `n`-এর উত্তরটা `n-1`-এর উত্তর *দিয়ে* বর্ণনা করো, তারপর `n-1` কীভাবে solve হয় সেটা ভাবা বন্ধ করো (leap of faith)।

Worked example — digit-এর যোগফল:

```python
def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)
```

472-এর উপর dry run: `2 + digit_sum(47)` = `2 + (7 + digit_sum(4))` = `2 + (7 + 4)` = `13`।

- **Problems:** Fibonacci Number <https://leetcode.com/problems/fibonacci-number/>, Reverse String <https://leetcode.com/problems/reverse-string/>, Climbing Stairs <https://leetcode.com/problems/climbing-stairs/>। — [Fibonacci Number: বাংলা নোট](problems/001-fibonacci-number.md), [Climbing Stairs: বাংলা নোট](problems/002-climbing-stairs.md), [Reverse String: বাংলা নোট](problems/003-reverse-string.md)

## Pattern 2: Divide-and-conquer

- **Trigger words:** "halves", "merge", "O(n log n) expected", "independent subparts"।
- **Core idea:** input-কে 2+ INDEPENDENT টুকরোয় ভাগ করো, প্রতিটা recursively solve করো, result-গুলো জোড়া লাগাও।
- **Inherits from:** decrease-and-conquer, upgrade হয়ে — 1 করে ছোট করার (depth n) বদলে অর্ধেক করে ছোট করো (depth log n)।
- **Thinking tweak:** speedup-টা থাকে COMBINE step-এ: অর্ধেক জোড়া লাগাতে O(n) লাগলে আর depth log n হলে, মোট হয় O(n log n)।

Worked example — fast power, O(log n):

```python
def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)
    return half * half if n % 2 == 0 else half * half * x
```

`power(3, 4)`-এর dry run: `power(3,2)` → `power(3,1)` → `power(3,0)=1` → উপরে: 1·1·3=3 → 3·3=9 → 9·9=81। Exponent 4-এর জন্য তিনটা recursive call।

- **Problems:** Pow(x, n) <https://leetcode.com/problems/powx-n/>, Merge Sort (concept — নিজে implement করো, তুলনা করো <https://leetcode.com/problems/sort-an-array/>-এর সাথে), Maximum Subarray <https://leetcode.com/problems/maximum-subarray/> (D&C variant)। — [Pow(x, n): বাংলা নোট](problems/005-pow-x-n.md)

## Pattern 3: Subsets — the include/exclude branch

- **Trigger words:** "all subsets", "power set", "প্রতিটা item নেওয়া বা না-নেওয়ার সব combination", "2^n"।
- **Core idea:** item-গুলোতে বাঁ থেকে ডানে হাঁটো; প্রতিটা item-এর জন্য ঠিক দুটো recursive call করো — একটায় নাও, একটায় বাদ দাও। 2 × 2 × ... × 2 leaf-গুলোই হলো 2^n subset।
- **Inherits from:** decrease-and-conquer (এখনো একবারে একটা item) — কিন্তু এবার single call-এর বদলে BRANCHING, যেটা call-এর লাইনটাকে call-এর tree বানিয়ে দেয়।
- **Thinking tweak:** "কোন কোন subset আছে?" ভাবা বন্ধ করো, ভাবো "এই একটা item-এর জন্য আমার option কী?" Locally দুটো option; globally সব subset বেরিয়ে আসে।

Worked example — `[1, 2]`-এর subsets:

```python
def subsets(nums):
    out = []
    def go(i, path):
        if i == len(nums):
            out.append(path[:])      # snapshot!
            return
        path.append(nums[i]); go(i + 1, path); path.pop()   # include
        go(i + 1, path)                                      # exclude
    go(0, [])
    return out

subsets([1, 2])    # [[1, 2], [1], [2], []]
```

Dry run: include 1 → include 2 → record [1,2] → pop → exclude 2 → record [1] → pop 1 → exclude 1 → include 2 → record [2] → pop → exclude → record []। (পুরো frame-by-frame আছে [visual-explanation.md](visual-explanation.md)-তে।)

- **Problems:** Subsets <https://leetcode.com/problems/subsets/>, Subsets II <https://leetcode.com/problems/subsets-ii/> (sort করো, তারপর EXCLUDE পাশে সমান প্রতিবেশীদের skip করো)। — [Subsets: বাংলা নোট](problems/007-subsets.md), [Subsets II: বাংলা নোট](problems/010-subsets-ii.md)

## Pattern 4: Permutations — choose each remaining

- **Trigger words:** "all orderings", "arrangements", "n!", "প্রতিটা item ঠিক একবার করে ব্যবহার করা প্রতিটা sequence"।
- **Core idea:** উত্তরটা slot ধরে ধরে বানাও; প্রতিটা slot-এ, এখনো ব্যবহার-না-হওয়া প্রতিটা item-এর উপর loop চালাও, বসাও, recurse করো, সরাও।
- **Inherits from:** subsets-এর branching — কিন্তু branching factor এখন "সব unused item" (n, তারপর n-1, ...), fixed 2 না, আর একটা used-tracker লাগে (একটা set — hello, [../05-hashing/](../05-hashing/README.md)-এর seen-set pattern)।
- **Thinking tweak:** recursion ঠিক করে তুমি কোন SLOT ভরছ; loop ঠিক করে তাতে কী যাচ্ছে। দুটো dimension, পরিষ্কারভাবে আলাদা।

Worked example — `[1, 2, 3]`-এর permutations:

```python
def permutations(nums):
    out, used = [], set()
    def go(path):
        if len(path) == len(nums):
            out.append(path[:])
            return
        for x in nums:
            if x in used:
                continue
            used.add(x); path.append(x)     # choose
            go(path)                        # explore
            path.pop(); used.discard(x)     # un-choose
    go([])
    return out
```

সম্পূর্ণ output order: `[1,2,3]`, `[1,3,2]`, `[2,1,3]`, `[2,3,1]`, `[3,1,2]`, `[3,2,1]`। প্রতিটি leaf-এর পরে pop করে আগের state ফেরত আসে। [পূর্ণ decision tree](problems/009-permutations.md) দেখে প্রতিটি branch অনুসরণ করো।

- **Problems:** Permutations <https://leetcode.com/problems/permutations/>, Permutations II <https://leetcode.com/problems/permutations-ii/>, Letter Combinations of a Phone Number <https://leetcode.com/problems/letter-combinations-of-a-phone-number/> (digit প্রতি choose, used-set লাগে না)। — [Letter Combinations of a Phone Number: বাংলা নোট](problems/008-letter-combinations-phone.md), [Permutations: বাংলা নোট](problems/009-permutations.md), [Permutations II: বাংলা নোট](problems/014-permutations-ii.md)

## Pattern 5: Combinations with pruning

- **Trigger words:** "combinations summing to target", "choose k of n", "আলাদা order-এ duplicate চলবে না", এমন time limit যেটা brute force উড়িয়ে দিত।
- **Core idea:** subsets-এর মতো, কিন্তু (a) একটা START INDEX চাপাও যাতে প্রতিটা combination একটাই canonical order-এ তৈরি হয়, আর (b) যে মুহূর্তে কোনো branch প্রমাণসহ ব্যর্থ, সেটা কেটে ফেলো।
- **Inherits from:** subsets (branch structure) + [../05-hashing/](../05-hashing/README.md)-এর complement thinking ("remaining target"-টাই সেই complement যেটা তোমার এখনো দরকার)।
- **Thinking tweak:** প্রতিটা node-এ জিজ্ঞেস করো "এই branch-এর কোনো descendant কি এখনো জিততে পারে?" না হলে — সাথে সাথে return। ভালো prune পুরো subtree মুছে দেয়, একটা একটা leaf না।

Worked example — `[2, 3, 5]` থেকে 8 sum-এর combinations (Combination Sum, নিজের ভাষায়: সংখ্যা বাছো, reuse চলবে, target-এ ঠিকঠাক পৌঁছাও):

```python
def combination_sum(cands, target):
    cands.sort()
    out = []
    def go(start, path, remaining):
        if remaining == 0:
            out.append(path[:]); return
        for i in range(start, len(cands)):
            if cands[i] > remaining:     # PRUNE: sorted, so all later fail too
                break
            path.append(cands[i])
            go(i, path, remaining - cands[i])   # i, not i+1: reuse allowed
            path.pop()
    go(0, [], target)
    return out

combination_sum([2, 3, 5], 8)   # [[2,2,2,2], [2,3,3], [3,5]]
```

Dry run-এর highlight: path=[2,2,2], remaining=2 → choose 2 → remaining 0 → record; remaining=2-তে ফিরে এসে candidate 3 trigger করে `3 > 2` → `break` এক কোপে 3-branch আর 5-branch দুটোকেই মেরে ফেলে। এটাই pruning-এর ভাড়া শোধ করা।

- **Problems:** Combination Sum <https://leetcode.com/problems/combination-sum/>, Combination Sum II <https://leetcode.com/problems/combination-sum-ii/>, Combinations <https://leetcode.com/problems/combinations/>। — [Combinations: বাংলা নোট](problems/011-combinations.md), [Combination Sum: বাংলা নোট](problems/012-combination-sum.md), [Combination Sum II: বাংলা নোট](problems/013-combination-sum-ii.md)

## Pattern 6: Constraint backtracking (N-Queens style)

- **Trigger words:** "place items so no two conflict", "board/grid validly ভরো", "satisfy all constraints", puzzles।
- **Core idea:** প্রতি level-এ একটা decision (প্রতি row-তে একটা queen, প্রতি step-এ একটা cell); recurse করার আগে CHECK করো partial state এখনো legal কি না; dead end-এ undo করে পরের option try করো।
- **Inherits from:** permutations (queen-দের column-গুলোই একটা permutation!) + pruning (legality check-টা আসলে প্রতিটা node-এ apply করা একটা prune)।
- **Thinking tweak:** validate করো তাড়াতাড়ি — কোনো partial placement নিয়ম ভাঙার মুহূর্তেই reject করো, পুরো candidate বানিয়ে শেষে test করার বদলে। Early check tree-টাকে n^n থেকে feasibility-র দিকে ছোট করে আনে।

Worked example — row `r`-এর queen কি column `c`-তে বসতে পারে? Attacked line-গুলো set-এ track করো (আবার সেই seen-set pattern):

```python
cols, diag1, diag2 = set(), set(), set()
# queen at (r, c) controls: column c, diagonal r-c, anti-diagonal r+c

def safe(r, c):
    return c not in cols and (r - c) not in diag1 and (r + c) not in diag2
```

4×4 board-এ queen আছে (0,0) ও (1,2)-তে। Row 2-এর প্রতিটি candidate:

| column | কেন বাদ |
| --- | --- |
| 0 | (0,0)-এর column |
| 1 | 2+1 = 1+2: (1,2)-এর anti-diagonal |
| 2 | (1,2)-এর column; (0,0)-এর diagonal-ও |
| 3 | 2−3 = 1−2: (1,2)-এর diagonal |

কোনো legal column নেই, তাই row 1-এর choice undo করো। [পূর্ণ search tree](problems/019-n-queens.md) ও [চলমান state-এর table](visual-explanation.md) পাশাপাশি দেখো।

- **Problems:** N-Queens <https://leetcode.com/problems/n-queens/>, Sudoku Solver <https://leetcode.com/problems/sudoku-solver/>, Word Search <https://leetcode.com/problems/word-search/>, CSES "Chessboard and Queens" — <https://cses.fi/problemset/task/1624/>। — [Word Search: বাংলা নোট](problems/017-word-search.md), [N-Queens: বাংলা নোট](problems/019-n-queens.md), [Chessboard and Queens: বাংলা নোট](problems/021-cses-chessboard-and-queens.md), [Sudoku Solver: বাংলা নোট](problems/022-sudoku-solver.md)

## Pattern 7: Memoization — the bridge to dynamic programming

- **Trigger words:** "overlapping subproblems", "recursion tree-তে node repeat হয়", "count the ways" ("list the ways" না), এমন recursion যেটা সঠিক কিন্তু খুব slow।
- **Core idea:** `f(args)` compute করার আগে একটা cache check করো; compute করার পর সেখানে store করো। প্রতিটা আলাদা subproblem ঠিক একবার solve হয়।
- **Inherits from:** recursion tree-র ছবি + [../05-hashing/](../05-hashing/README.md)-এর hash-map lookup — cache-টা আসলে call-এর argument দিয়ে key করা একটা dict।
- **Thinking tweak:** জিজ্ঞেস করো "উত্তরটা কি পুরোপুরি argument-গুলো দিয়েই নির্ধারিত?" হ্যাঁ হলে (pure function) আর argument repeat করলে, memoize করো। Listing-all problem-গুলো (subsets, permutations) লাভ পায় না — তাদের output-গুলো সব আলাদা; counting/optimum problem-গুলো পায়।

Worked example — fib, তিন লাইনের বদলে exponential থেকে linear:

```python
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
```

`fib(5)`-এর dry run: fib(0..5) প্রতিটা একবার করে compute হয় = 6টা আসল computation; naive version n=5-এ 15টা call করে আর n=30-এ ~2.7 million। Code-এর আকার একই, শুধু dict-আকৃতির memory লাগানো।

Manual version (যাতে জাদুটা দেখা যায়):

```python
def fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]
```

এটাই "top-down DP"। এটাকে উল্টে bottom-up table-ভরা একটা loop বানাও — তুমি পৌঁছে গেছ [../12-dynamic-programming/](../12-dynamic-programming/README.md)-এ; ওই পুরো section এই pattern-এরই বড় হয়ে ওঠা রূপ।

- **Problems:** Climbing Stairs <https://leetcode.com/problems/climbing-stairs/>, Fibonacci Number <https://leetcode.com/problems/fibonacci-number/>, তারপর graduate করো House Robber <https://leetcode.com/problems/house-robber/>-এ, DP section-এ। — [Fibonacci Number: বাংলা নোট](problems/001-fibonacci-number.md), [Climbing Stairs: বাংলা নোট](problems/002-climbing-stairs.md)

## The inheritance map

```
loops
  │
  ▼
decrease-and-conquer ──► divide-and-conquer (shrink by half)
  │
  ▼ (branch instead of single call)
subsets (include/exclude)
  │
  ├──► permutations (branch = all unused; needs seen-set from 05-hashing)
  │         │
  │         ▼
  │    constraint backtracking (permutations + early validity pruning)
  │
  └──► combinations with pruning (subsets + start index + cut hopeless branches)

recursion tree with repeats ──► memoization ──► ../12-dynamic-programming/
```

পরের ধাপ: [implementation.py](./implementation.py) চালাও, তারপর খোলো [problems/README.md](./problems/README.md)।