Skip to content

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-এর যোগফল:

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।

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):

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।

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:

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-তে।)

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/-এর seen-set pattern)।
  • Thinking tweak: recursion ঠিক করে তুমি কোন SLOT ভরছ; loop ঠিক করে তাতে কী যাচ্ছে। দুটো dimension, পরিষ্কারভাবে আলাদা।

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

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

Dry run-এর শুরু: choose 1 → choose 2 → choose 3 → record [1,2,3] → unwind করে [1] → choose 3 → choose 2 → record [1,3,2] → ... মোট 6টা result (3! = 6)।

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/-এর 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-এ ঠিকঠাক পৌঁছাও):

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-এর ভাড়া শোধ করা।

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):

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

4x4-এর উপর dry run: queen আছে (0,0) আর (1,2)-তে → row 2-র candidate: c=0 col-blocked, c=1 কি (1,2)-র diag-এ পড়ে? r-c=1 vs 1-2=-1 না, r+c=3 vs 1+2=3 হ্যাঁ blocked, c=2 col-blocked, c=3 কি (1,2)-র anti-diag? 2+3=5 না, কিন্তু (0,0)-র diag: 2-3=-1 vs 0... safe? 2-3=-1, 0-0=0, 1-2=-1 → (1,2)-র কারণে blocked। চারটাই fail → backtrack (ঠিক এই dead end-টাই visual-explanation.md-তে animate করা)। পুরো solver আছে implementation.py-তে।

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/-এর 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:

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 (যাতে জাদুটা দেখা যায়):

def fib_memo(n, 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/-এ; ওই পুরো section এই pattern-এরই বড় হয়ে ওঠা রূপ।

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 চালাও, তারপর খোলো problems/README.md।