011 — Combinations¶

Source¶

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

1. Problem in simple words¶

দুটো সংখ্যা 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))

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

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

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

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।

8. Example input and 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টা)

9. Brute force thinking¶

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

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

10. Why brute force is slow¶

এই 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-এ ঢোকেই না।

11. Key observation¶

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

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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টা।

15. Python solution¶

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!")

16. Line-by-line code explanation¶

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 হয়।

17. Output walkthrough¶

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!।

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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।

21. Which basic problem this inherits from¶

ভিত্তি: 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)-এর ভিত্তি।

22. Similar harder problems¶

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)

23. Pattern learned¶

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

24. Final summary¶

ভবিষ্যতের আমাকে: "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।