011 — Combinations¶

Problem link ও উৎস

Original source: Classic backtracking exercise (choose k of n)
Platform: LeetCode — https://leetcode.com/problems/combinations/
Topic: recursion / backtracking (start-index combinations)
Difficulty: Medium
Pattern: start-index combinations — fixed size k, প্রতিটা combination একটাই বাড়ন্ত ক্রমে
Basic idea inherited from: Fixed size k সহ subsets

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

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

দুটো সংখ্যা n আর k দেওয়া আছে। তোমার কাজ: 1 থেকে n পর্যন্ত সংখ্যাগুলো থেকে ঠিক kটা সংখ্যার সব combination বের করা। এখানে order গুরুত্বহীন — [1, 2] আর [2, 1] একই combination, তাই প্রতিটাকে একবারই গোনা হয় (সাধারণত বাড়ন্ত ক্রমে লেখা)। Subsets-এ সব মাপের subset লাগত; এখানে শুধু মাপ ঠিক k এমনগুলো।

উদাহরণ

n = 4, k = 2
combinations = [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]   (মোট 6 = C(4,2))

Input ও output¶

উদাহরণ

Input : n=4, k=2 -> Output: [1,2],[1,3],[1,4],[2,3],[2,4],[3,4]   (6টা)
Input : n=3, k=3 -> Output: [1,2,3]                                (1টা)

Edge case 1 (k=1):   n=4, k=1 -> Output: [1],[2],[3],[4]          (4টা)
Edge case 2 (k=n):   n=1, k=1 -> Output: [1]                       (1টা)

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

একটা দলের 4 জন বন্ধু থেকে 2 জনের কমিটি বানানোর কথা ভাবো। "রাহুল আর মীরা" আর "মীরা আর রাহুল" একই কমিটি — তাই গণনায় একবারই ধরো। সবসময় তালিকার আগের নাম আগে লিখলে (বাড়ন্ত ক্রম) প্রতিটা জোড়া স্বাভাবিকভাবেই একবার করে আসে; সেটাই start-index-এর কাজ।

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

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

ভিত্তি হলো Subsets, কিন্তু মাপ fixed k। Subsets সব মাপের সংগ্রহ দিত (2^n); এখানে শুধু ঠিক k-মাপের চাই। তাই দুটো ছোট পরিবর্তন: (1) base case এখন len(path) == k (সব index পেরোনো নয়), আর (2) order গুরুত্বহীন বলে একটা start index চাপাই — যাতে প্রতিটা combination কেবল বাড়ন্ত ক্রমে একবারই তৈরি হয়, [2,1]-এর মতো নকল আসে না।

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

লুকানো math হলো binomial coefficient C(n, k) = n! / (k!·(n-k)!) — n থেকে k বেছে নেওয়ার রকম-সংখ্যা, যেখানে order গোনা হয় না। start index দিয়ে আমরা প্রতিটা subset-কে তার বাড়ন্ত-ক্রম প্রতিনিধি দিয়ে গড়ি, ফলে permutation-এর k! গুণ অতিরিক্ত গণনা স্বয়ংক্রিয়ভাবে বাদ পড়ে — গাছের গঠনই duplicate দমন করে।

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

একটা list path (বর্তমান combination গড়তে), একটা list out (সব combination জমাতে), একটা integer start (পরবর্তী পছন্দ কোথা থেকে শুরু), আর recursion-এর জন্য call stack। record করার সময় path[:] snapshot।

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

start integer-টাই এখানে আসল নায়ক: এটা নিশ্চিত করে আমরা কখনো পিছনের সংখ্যায় ফিরি না, তাই প্রতিটা combination শুধু বাড়ন্ত ক্রমে গড়ে — duplicate ঠেকাতে কোনো set বা skip-line লাগে না, শুধু একটা integer। path mutable বলে append/pop O(1), পুরো গাছ জুড়ে একটাই working combination reuse হয়।

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

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: Subsets চালিয়ে 1..n-এর সব 2^nটা subset গড়ো, তারপর শুধু যেগুলোর দৈর্ঘ্য ঠিক k সেগুলো রাখো।

উদাহরণ

out = [s for s in subsets(range(1, n+1)) if len(s) == k]

কোথায় বেশি কাজ হচ্ছে¶

এই version সবসময় পুরো 2^nটা subset গড়ে, অথচ আমরা চাই মাত্র C(n, k)টা। বেশিরভাগ মাপ ভুল হওয়ায় ছুঁড়ে ফেলা হয় — যেমন n=20, k=2-এ 2^20 ≈ 10 লক্ষ গড়ে মাত্র 190টা রাখা হয়। start-index version base case-এ len == k দেখে থেমে যায় আর kটা item পূর্ণ হলেই গভীরে আর নামে না, তাই সরাসরি C(n,k)টাই গড়ে — বাকি branch-এ ঢোকেই না।

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

মূল observation: order গুরুত্বহীন combination = বাড়ন্ত-ক্রমের subset। [2,1]-কে [1,2]-এর নকল হিসেবে আলাদা করে ঠেকানোর দরকার নেই — শুধু সবসময় বড় index-এর দিকে এগোও (start)। আর "k-মাপ" condition base case-এ বসিয়ে দিলে গাছটা গভীরে k level-এর বেশি যায় না।

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

go(start, path): base case len(path) == k হলে snapshot record। নাহলে i start থেকে n পর্যন্ত: append (choose), go(i+1, path) (explore), pop (un-choose)। i+1 মানে প্রতিটা সংখ্যা একবার আর সবসময় বাড়ন্ত ক্রম। চাইলে pruning: যদি বাকি সংখ্যা (n - i + 1) থেকে প্রয়োজনীয় বাকি (k - len(path)) পূরণ না হয়, loop আগেই থামাও — for i in range(start, n - (k - len(path)) + 2)।

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

মোচড়: "n থেকে k বাছার সব রকম" বিশাল ভেবো না; ভাবো "এখন একটা সংখ্যা নিচ্ছি, পরেরটা অবশ্যই এর চেয়ে বড় হবে।" এই "সবসময় সামনে এগোও" নিয়মটাই order-গুরুত্বহীনতা সামলায় — duplicate-এর চিন্তা পুরো উবে যায়, শুধু start বাড়াও।

ছবিতে বোঝা¶

start-index loop, base case len == k। n = 4, k = 2-এর decision tree:

উদাহরণ

                         go(1, [])
        1 /          2 |        3 |        \ 4 (k বাকি নেই -> ফলহীন)
   go(2,[1])    go(3,[2])   go(4,[3])
   2/ 3| 4\      3| 4\        4|
[1,2][1,3][1,4] [2,3][2,4]   [3,4]

leaf (len(path) == k = 2) = 6 = C(4,2) combination।

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

combine(4, 2), go(start, path):

go(1,[]): i=1: append → go(2,[1])।
go(2,[1]): len<2। i=2: record [1,2]; i=3: [1,3]; i=4: [1,4]; pop 1।
go(1,[]): i=2: append → go(3,[2]): i=3: [2,3]; i=4: [2,4]; pop।
go(1,[]): i=3: append → go(4,[3]): i=4: [3,4]; pop।
go(1,[]): i=4: append → go(5,[4]): i range খালি, কোনো leaf নয়।
out = [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] — 6টা।

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

Python¶

Python

def combine(n, k):
    out = []
    def go(start, path):
        if len(path) == k:            # base case: k-মাপ পূর্ণ
            out.append(path[:])       # snapshot!
            return
        for i in range(start, n + 1): # start থেকে: সবসময় বাড়ন্ত ক্রম
            path.append(i)            # CHOOSE
            go(i + 1, path)           # EXPLORE (i+1: পরেরটা বড় হবে)
            path.pop()                # UN-CHOOSE
    go(1, [])
    return out

# ---- order-independent তুলনার helper ----
def norm(list_of_lists):
    return sorted([sorted(s) for s in list_of_lists])

# ---- tests ----
assert norm(combine(4, 2)) == norm(
    [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])
assert len(combine(4, 2)) == 6                  # C(4,2)
assert combine(3, 3) == [[1, 2, 3]]             # k = n -> একটাই
assert norm(combine(4, 1)) == norm([[1], [2], [3], [4]])
assert combine(1, 1) == [[1]]
assert len(combine(5, 3)) == 10                 # C(5,3)
print("সব test pass!")

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

if len(path) == k: — base case: ঠিক kটা সংখ্যা জমে গেছে, একটা পূর্ণ combination।
out.append(path[:]) — snapshot; live path পরে বদলাবে।
for i in range(start, n + 1): — start থেকে শুরু বলে আর কখনো পিছনে ফিরি না — বাড়ন্ত ক্রম নিশ্চিত।
path.append(i) — CHOOSE: এই সংখ্যা নিলাম।
go(i + 1, path) — EXPLORE: পরের পছন্দ i+1 থেকে, তাই পরেরটা সবসময় বড়।
path.pop() — UN-CHOOSE: undo, যাতে পরের i পরিষ্কারভাবে try হয়।

Output মিলিয়ে দেখা¶

combine(4,2): প্রতিটা leaf-এ (len==2) একটা combination record হয়; start-index বড়-index-এর দিকে এগোয় বলে [2,1]-এর মতো নকল কখনো তৈরি হয় না। ফল 6টা (=C(4,2))। order গুরুত্বহীন, তাই norm-এ sorted-of-sorted করে তুলনা — assert stable। k=n-এ একটাই, k=1-এ n-টা, C(5,3)=10। সব মিলে print: সব test pass!।

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

সময়¶

O(k · C(n, k)) — C(n, k)টা combination, প্রতিটার snapshot নিতে k পর্যন্ত copy। pruning থাকলে গাছ আরও ছোট।

অতিরিক্ত জায়গা¶

Output বাদ দিলে O(k) — path ও call stack-এর গভীরতা k পর্যন্ত। Output ধরলে O(k · C(n, k))।

যে ভুলগুলো এড়াতে হবে¶

start ব্যবহার না করে প্রতিবার 1..n loop — তখন [1,2] আর [2,1] দুটোই আসে (combination নয়, permutation)।
go(i+1)-এর বদলে go(start) বা go(i) — হয় duplicate, নয় reuse; combination-এ প্রতিটা একবার ও সামনে এগোনো চাই।
base case len(path) == k-এর বদলে start > n দেওয়া — তখন সব মাপের subset বেরোয়, fixed-k নয়।
out.append(path) snapshot ছাড়া — সব entry একই live list-এর reference।

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

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

ভিত্তি: Subsets (এই tracker-এর #7), এখানে fixed size k + start-index। ../patterns.md-এর Pattern 5 (Combinations with pruning)-এ start-index-এর ভূমিকা ব্যাখ্যা করা — "প্রতিটা combination একটাই canonical order-এ তৈরি"। এই start-index কঙ্কালই পরের Combination Sum (#12) আর Combination Sum II (#13)-এর ভিত্তি।

পরের অনুশীলন¶

Combination Sum (start-index + reuse + target) — https://leetcode.com/problems/combination-sum/ (এই tracker-এর #12)
Combination Sum II (start-index + sort-skip + target) — https://leetcode.com/problems/combination-sum-ii/ (#13)
Subsets (সব মাপ) — https://leetcode.com/problems/subsets/ (#7)

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

Start-index combinations: order-গুরুত্বহীন k-মাপ সংগ্রহ গড়তে একটা start integer দিয়ে সবসময় বাড়ন্ত ক্রমে এগোও, base case-এ len == k; এতে duplicate স্বয়ংক্রিয়ভাবে বাদ — সব "choose k of n / combinations summing to X" problem-এর কঙ্কাল।

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

ভবিষ্যতের আমাকে: "Combinations = Subsets + start-index (সবসময় সামনে এগোও) + base case len == k।" যখনই 'n থেকে k বাছো' বা 'order গোনা হবে না এমন combination' শুনবে — এই start-index skeleton মনে করবে; i+1 দিয়ে recurse করা মানেই duplicate-মুক্ত বাড়ন্ত ক্রম।

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