কনটেন্টে যান

019 — Path Sum II

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে একটা binary tree আর একটা target সংখ্যা দেওয়া আছে। তোমার কাজ: এমন সব root-to-leaf path খুঁজে বের করা যেগুলোর node-value-র যোগফল ঠিক target-এর সমান। প্রতিটা path একটা list, আর সব path-এর একটা list-of-lists ফেরত দিতে হবে।

উদাহরণ
            5
           / \
          4   8        target = 22
         /   / \
        11  13  4      path 5→4→11→2 = 22 ✓
       /  \      \      path 5→8→4→1 = 18 ✗ (এই tree-তে অন্য সংখ্যায়)
      7    2      1

Input ও output

উদাহরণ
Input : root = [5,4,8,11,null,13,4,7,2,null,null,null,1], target = 22
Output: [[5, 4, 11, 2]]

Input : root = [1,2,3], target = 3      -> Output: [[1, 2]]
Input : root = [1,2,3], target = 4      -> Output: [[1, 3]]
Edge  : root = [], target = 0           -> Output: []        (path নেই)
Edge  : root = [1,2], target = 1        -> Output: []        (1 leaf না)

চেনা উদাহরণে বোঝা

একটা গোলকধাঁধায় তুমি সূতো বিছিয়ে এগোচ্ছ — প্রতিটা মোড়ে সূতো বাড়ছে (choose), গন্তব্যে পৌঁছে যদি ঠিক হয় তবে পুরো রুটের একটা ছবি তুলে রাখছ (copy), আর ফিরে আসার সময় সেই অংশের সূতো গুটিয়ে নিচ্ছ (un-choose) যাতে পরের শাখা পরিষ্কার থেকে শুরু হয়। সূতোটাই তোমার path।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা Path Sum (#8)-এর উপর গড়ে ওঠে: সেখানে শুধু হ্যাঁ/না জানতে চাওয়া হতো "এমন কোনো path আছে কি?"। এখানে আমরা সব matching path জমাতে চাই, তাই যোগ হয় ../../06-recursion-and-backtracking/-এর choose / explore / un-choose শৃঙ্খলা — নামার পথে node-টা path-এ append করো, ফেরার পথে pop করো।

ভেতরের যুক্তি

লুকানো logic দুই অংশ — carry-down state আর backtracking:

উদাহরণ
নামার পথে: path-এ node যোগ করো, remaining = target - node.val
leaf-এ: remaining == 0 হলে path-এর একটা copy সংরক্ষণ করো
ফেরার পথে: path থেকে node সরাও (un-choose)

মূল গণিত হলো decrease-and-conquer (remaining কমতে থাকে), আর মূল শৃঙ্খলা হলো backtracking — একই path list সব branch-এ পুনর্ব্যবহার করতে।

কী দিয়ে তথ্য রাখব

একটা list path (বর্তমান root-to-current chain ধরে রাখে, append/pop দিয়ে), recursion call stack (কোন path-এ আছি মনে রাখে), আর একটা result list (matching path-গুলোর copy জমায়)।

এটি কেন উপযুক্ত

একটা মাত্র path list সব branch-এ পুনর্ব্যবহার করা সবচেয়ে কম-খরচের — নামার সময় append, ফেরার সময় pop, তাই প্রতিটা মুহূর্তে path-এ ঠিক বর্তমান chain থাকে। কিন্তু leaf-এ match পেলে অবশ্যই path[:] (একটা copy) result-এ দিতে হবে, কারণ পরে pop হয়ে গেলে মূল list বদলে যাবে।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: tree-র সব root-to-leaf path আলাদা করে বের করি (প্রতিটা পুরো list বানিয়ে), তারপর প্রতিটার যোগফল মেপে target-এর সমান হলে রাখি।

উদাহরণ
1) সব path বের করো: [5,4,11,7], [5,4,11,2], [5,8,13], [5,8,4,1]
2) প্রতিটার যোগ: 27, 22, 26, 18
3) target 22-এর সমানগুলো রাখো: [[5,4,11,2]]

কোথায় বেশি কাজ হচ্ছে

প্রতিটা path আলাদা করে নতুন করে বানালে অনেক path-এর shared উপরের অংশ (যেমন [5,4,11]) বারবার তৈরি হয় — extra memory আর কাজ নষ্ট। Backtracking একই path list পুনর্ব্যবহার করে: শুধু এক node append/pop করে, পুরো prefix প্রতিবার নতুন করে বানায় না। Match পেলেই কেবল একটা copy নেয়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: একই path list সব শাখায় চালানো যায়, যদি নামার সময় append আর ফেরার সময় pop করা হয় (backtracking)। আর leaf-এ match পেলে অবশ্যই একটা copy (path[:]) সংরক্ষণ করতে হবে — সরাসরি path রাখলে পরে pop হয়ে সেটা নষ্ট হয়ে যাবে।

আরও কম কাজে সমাধান

এটা path + backtracking: DFS-এ নামার সময় path.append(node.val) আর remaining -= node.val; leaf-এ remaining == 0 হলে result.append(path[:]); দুই child-এ recurse করার পর path.pop() (un-choose)। প্রতিটা node একবার দেখা হয়; matching path copy করার খরচ আলাদা, কিন্তু সেটা অনিবার্য (output-এর আকার)।

ভাবনার পরিবর্তন

মোচড়: "প্রতিটা path আলাদা করে বানাব" ভাবা বন্ধ করো। বরং ভাবো "একটাই path list রাখব, এগোলে বাড়াব, ফিরলে কমাব।" আর সবচেয়ে গুরুত্বপূর্ণ: match পেলে copy রাখো — কারণ মূল list-টা পরে বদলে যাবে। choose → explore → un-choose ছন্দটাই মূল।

ছবিতে বোঝা

Input tree-এর সব node নিচে আছে। target=22; root থেকে leaf পর্যন্ত যোগফল 22 হলেই শুধু path নেব।

flowchart TD
  n5["5"] --> n4["4"]
  n5 --> n8["8"]
  n4 --> n11["11"]
  n11 --> n7["7"]
  n11 --> n2["2"]
  n8 --> n13["13"]
  n8 --> r4["4"]
  r4 --> n1["1"]
DFS-এ শেষ হওয়া leaf-path Sum ফল
[5,4,11,7] 27 বাদ; 7 pop করলে path [5,4,11]
[5,4,11,2] 22 Copy রাখুন; 2 pop করলে [5,4,11]
[5,8,13] 26 বাদ; 13 pop করলে [5,8]
[5,8,4,1] 18 বাদ; 1 pop করলে [5,8,4]

বাঁ subtree শেষ হলে 11 ও 4 pop করে path আবার [5] হয়; তারপর 8-এ নামি। ডান subtree শেষ হলে 4, 8, 5 ফেরার সময় pop হয়। শেষে working path খালি, কিন্তু copy করা result [[5,4,11,2]] অক্ষত থাকে।

ছোট input-এ ধাপে ধাপে

Input ছোট tree [1,2,3], target = 3:

  1. dfs(1, rem=3, path=[]): append 1 → path [1], rem = 2। 1 leaf না।
  2. dfs(2, rem=2, path=[1]): append 2 → path [1,2], rem = 0। 2 leaf, rem==0 → copy [1, 2] সংরক্ষণ। pop → path [1]।
  3. dfs(3, rem=2, path=[1]): append 3 → path [1,3], rem = -1। 3 leaf, rem ≠ 0 → কিছু না। pop → path [1]।
  4. pop 1 → path []। result = [[1, 2]]।

কোড ও ব্যাখ্যা

Python

Python
from collections import deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(values):
    """level-order list (None = missing child) থেকে tree বানায়।"""
    if not values:
        return None
    root = TreeNode(values[0])
    q = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1
    return root


def path_sum(root, target):
    result, path = [], []

    def dfs(node, remaining):
        if node is None:                 # খালি subtree: কোনো path নেই
            return
        path.append(node.val)            # choose
        remaining -= node.val
        if node.left is None and node.right is None and remaining == 0:
            result.append(path[:])       # leaf-এ ঠিক যোগ → copy সংরক্ষণ
        else:
            dfs(node.left, remaining)    # explore বাঁ দিক
            dfs(node.right, remaining)   # explore ডান দিক
        path.pop()                       # un-choose (backtrack)

    dfs(root, target)
    return result


# ---- tests ----
big = build_tree([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1])
assert path_sum(big, 22) == [[5, 4, 11, 2]]
assert path_sum(build_tree([1, 2, 3]), 3) == [[1, 2]]
assert path_sum(build_tree([1, 2, 3]), 4) == [[1, 3]]
assert path_sum(build_tree([]), 0) == []
assert path_sum(build_tree([1, 2]), 1) == []     # 1 leaf না, তাই match না
print("সব test pass!")

কোডের প্রতিটি অংশ

  • result, path = [], [] — matching path-এর copy জমাবে result; বর্তমান chain রাখবে path।
  • if node is None: return — খালি subtree, কিছু করার নেই।
  • path.append(node.val) — choose: এই node বর্তমান path-এ যোগ করো।
  • remaining -= node.val — target থেকে এই value বাদ; কত আর বাকি।
  • if ... leaf and remaining == 0: result.append(path[:]) — leaf-এ ঠিক যোগ মিললে path-এর একটা copy রাখো (সরাসরি path না, কারণ পরে বদলাবে)।
  • dfs(node.left/right, remaining) — explore: দুই দিকে নামো।
  • path.pop() — un-choose: ফেরার পথে এই node সরিয়ে দাও, যাতে পরের শাখা পরিষ্কার থেকে শুরু হয়।

Output মিলিয়ে দেখা

build_tree([5,4,8,11,None,13,4,7,2,None,None,None,1]) ওই ছবির tree বানায়; path_sum(big, 22) [[5, 4, 11, 2]] ফেরত দেয় — assert pass। [1,2,3] target 3 দেয় [[1, 2]], target 4 দেয় [[1, 3]], খালি tree দেয় [], আর [1,2] target 1 দেয় [] (1 leaf না) — সব pass। শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল

সময়

O(n²) সবচেয়ে খারাপ ক্ষেত্রে — প্রতিটা node একবার visit (O(n)), কিন্তু matching path copy করতে প্রতিটা O(n) লম্বা হতে পারে আর O(n) সংখ্যক path থাকতে পারে। শুধু traversal O(n); copy-র খরচ output-এর আকারের সমান।

অতিরিক্ত জায়গা

O(h) auxiliary — recursion call stack আর path list দুটোই height h-এর সমান গভীর/লম্বা হয়। (output result আলাদা, তার আকার matching path-এর মোট দৈর্ঘ্যের সমান।)

যে ভুলগুলো এড়াতে হবে

  • match পেলে result.append(path) (copy ছাড়া) লেখা — পরে pop হয়ে গেলে সব সংরক্ষিত reference খালি/ভুল হয়ে যায়; path[:] লাগবে।
  • path.pop() ভুলে যাওয়া — তখন path পরের শাখায়ও পুরোনো node বয়ে নিয়ে যায়, সব উত্তর ভুল।
  • leaf check ভুল করা: শুধু remaining == 0 দেখা যথেষ্ট না; node-টা সত্যিই leaf (দুই child None) হতে হবে, কারণ এটা root-to-leaf path।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: Path Sum (#8)-এর carry-down remaining আর ../../06-recursion-and-backtracking/-এর choose/explore/un-choose; traversal-patterns.md-র Pattern A (path problems)-ও এটাই। হ্যাঁ/না থেকে "সব path জমাও"-তে যেতে শুধু backtracking যোগ হয়।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Path collection with backtracking: একটাই path list রাখো; নামার সময় append (choose), শর্ত মিললে leaf-এ একটা copy সংরক্ষণ করো, ফেরার সময় pop (un-choose)। সব root-to-leaf path-জাতীয় problem-এর কঙ্কাল এটাই — copy নেওয়া আর pop করা ভুললেই bug।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "সব matching path = একটা path list-এ append/pop, leaf-এ match পেলে path[:] copy রাখো।" choose → explore → un-choose ছন্দ আর copy-নেওয়া — এই দুটোই মূল। 'সব path / সব combination জমাও' টাইপ tree problem দেখলেই এই backtracking চালটা মনে করবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।