012 — Combination Sum

Problem link ও উৎস

• Original source: Classic backtracking exercise (combinations summing to target)
• Platform: LeetCode — https://leetcode.com/problems/combination-sum/
• Topic: recursion / backtracking (combinations with pruning)
• Difficulty: Medium
• Pattern: combinations with pruning — start-index + reuse, sorted হলে target ছাড়ালে break
• Basic idea inherited from: Combinations + remaining-target complement

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

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

আলাদা ধনাত্মক সংখ্যার একটা list candidates আর একটা target দেওয়া আছে। তোমার কাজ: এমন সব সংগ্রহ বের করা যাদের যোগফল ঠিক target — আর প্রতিটা সংখ্যা যতবার খুশি ব্যবহার করা যায় (reuse allowed)। order গুরুত্বহীন, তাই [2, 3] আর [3, 2] একই, একবার গোনা। Combinations-এ মাপ fixed ছিল; এখানে মাপ যাই হোক, যোগফল = target এই শর্তটাই আসল।

উদাহরণ

candidates = [2, 3, 6, 7], target = 7
combinations = [2, 2, 3], [7]   (2+2+3 = 7, এবং 7 = 7)

Input ও output

উদাহরণ

Input : [2,3,6,7], target=7 -> Output: [2,2,3], [7]
Input : [2,3,5],   target=8 -> Output: [2,2,2,2], [2,3,3], [3,5]

Edge case 1 (অসম্ভব): [2], target=1 -> Output: []      (1 বানানো যায় না)
Edge case 2 (একই বারবার): [1], target=2 -> Output: [[1,1]]

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

খুচরো পয়সা দিয়ে ঠিক একটা দাম মেটানোর কথা ভাবো, যেখানে প্রতিটা মানের পয়সা অসীম সংখ্যায় আছে (reuse)। তুমি একটা পয়সা দিলে বাকি দেনা কমে; সেই কম দেনাটা একই সমস্যা, ছোট হয়ে। আর হাতের সবচেয়ে ছোট পয়সাও যদি বাকি দেনার চেয়ে বড় হয়, তখন আর কিছু দিয়েই হবে না — থেমে যাও (prune)।

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

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

ভিত্তি হলো Combinations + remaining-target complement। Combinations-এর মতোই একটা start index দিয়ে বাড়ন্ত ক্রমে এগোই (duplicate সংগ্রহ ঠেকাতে)। নতুন দুটো জিনিস: (1) base case এখন remaining == 0 (মাপ নয়, যোগফল), আর (2) reuse allowed বলে recurse করি go(i, ...) দিয়ে — i+1 নয়, যাতে একই সংখ্যা আবার নেওয়া যায়। "remaining target" হলো সেই complement যেটা ../../05-hashing/-এর complement-thinking থেকে আসে — এখনো কতটা যোগফল দরকার।

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

লুকানো logic হলো target-কে subtraction দিয়ে ছোট করা: একটা সংখ্যা c নিলে সমস্যাটা হয়ে যায় "remaining - c যোগফল কীভাবে বানাব?" — একই সমস্যা, ছোট target-এ। sort করা থাকলে একটা শক্তিশালী pruning খোলে: কোনো candidate remaining-এর চেয়ে বড় হলে, তার পরের সবগুলোও বড় (sorted), তাই পুরো লেজটা break দিয়ে কেটে ফেলা যায় — একটা একটা করে skip নয়, এক কোপে।

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

একটা list path (বর্তমান সংগ্রহ গড়তে), একটা list out (সব সংগ্রহ জমাতে), একটা integer remaining (এখনো কত যোগফল বাকি — running complement), আর recursion-এর জন্য call stack। sort করার জন্য candidate list-টা আগে sort করি যাতে pruning খাটে। record-এ path[:] snapshot।

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

remaining integer-টা প্রতি level-এ "আর কত দরকার" বলে দেয় — base case (==0) আর prune (candidate > remaining) দুটোই এই একটা সংখ্যা দেখেই হয়, পুরো path যোগ করে দেখার দরকার নেই। sorted list-এ > test-এর পর break বৈধ কারণ পরেরগুলো নিশ্চিত আরও বড়। path mutable বলে append/pop O(1)।

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

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

প্রথম সরল চিন্তা: যেহেতু reuse চলে আর target সীমিত, প্রতিটা candidate-এর জন্য 0..(target/c) বার নেওয়ার সব সমন্বয় চেষ্টা করো; প্রতিটার যোগফল দেখো।

উদাহরণ

for count of candidate[0] in 0..target//c0:
    for count of candidate[1] in 0..remaining//c1:
        ... (candidate যত, nested loop তত)
            if total == target: record

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

এই nested-count version-এ loop-সংখ্যা candidate-সংখ্যার সমান, আর প্রতিটা loop target পর্যন্ত যেতে পারে — অনেক সমন্বয় target ছাড়িয়ে গিয়েও তৈরি হয়, তারপর বাতিল হয়। আসল অপচয়: target পেরিয়ে যাওয়ার অনেক পরেও গণনা চলতে থাকে। recursion + sorted-break ঠিক যে মুহূর্তে candidate remaining ছাড়ায় সেই মুহূর্তেই পুরো subtree কেটে দেয়, তাই কখনো target ছাড়ানো শাখায় গভীরে নামে না।

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

মূল observation: একটা সংখ্যা নেওয়া = target থেকে সেটা বিয়োগ করে একই সমস্যা ছোট করা, আর reuse মানে নেওয়ার পরেও একই index থেকে আবার শুরু করা যায়। দ্বিতীয় observation: sort করা থাকলে candidate > remaining হওয়া মাত্র লুপ break — কারণ পরের সবগুলো আরও বড়, তারাও fail করবে। এই prune-ই brute force আর backtracking-এর গতির পার্থক্য।

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

candidates.sort() করো। go(start, path, remaining): remaining == 0 হলে snapshot record। নাহলে i start থেকে: যদি candidates[i] > remaining হয় break (sorted prune)। নাহলে append (choose), go(i, path, remaining - candidates[i]) (explore — i, কারণ reuse allowed), pop (un-choose)। start duplicate সংগ্রহ ঠেকায়, i (i+1 নয়) reuse খোলে, break hopeless লেজ কাটে।

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

মোচড়: "কোন কোন সংখ্যার সংগ্রহ target দেয়?" — পুরোটা একসাথে না ভেবে ভাবো "একটা সংখ্যা নিলে বাকি target কত, আর সেই ছোট target কীভাবে বানাব?" target-টাকেই recursion-এর সঙ্কুচিত-হতে-থাকা state বানাও। আর reuse মানে শুধু একটাই বদল: পরের call-এ i+1 নয়, i — একই সংখ্যায় থেকে যাওয়ার অনুমতি।

ছবিতে বোঝা

candidates=[2,3,6,7], target 7। সব বৈধ recursive call এখানে আছে। candidate > remaining হলে sorted হওয়ায় সেটি এবং তার পরের বড় candidate-গুলো বাদ যায়।

graph TD
  c0["[]; left=7; search"]
  c1["[2]; left=5; search"]
  c2["[2, 2]; left=3; search"]
  c3["[2, 2, 2]; left=1; dead end"]
  c2 -->|"2"| c3
  c4["[2, 2, 3]; left=0; record"]
  c2 -->|"3"| c4
  c1 -->|"2"| c2
  c5["[2, 3]; left=2; dead end"]
  c1 -->|"3"| c5
  c0 -->|"2"| c1
  c6["[3]; left=4; search"]
  c7["[3, 3]; left=1; dead end"]
  c6 -->|"3"| c7
  c0 -->|"3"| c6
  c8["[6]; left=1; dead end"]
  c0 -->|"6"| c8
  c9["[7]; left=0; record"]
  c0 -->|"7"| c9

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

combination_sum([2, 3, 6, 7], 7) (sort করা একই), go(start, path, remaining):

1. go(0,[],7): i=0 (2): append → go(0,[2],5)।
2. go(0,[2],5): i=0 (2): → go(0,[2,2],3)।
3. go(0,[2,2],3): i=0 (2): → go(0,[2,2,2],1): i=0 (2>1) → break, dead; pop।
4. go(0,[2,2],3): i=1 (3, =remaining): → go(1,[2,2,3],0): record [2,2,3]; pop।
5. unwind করে root-এর i=3 (7, =remaining): → go(3,[7],0): record [7]।
6. out = [[2,2,3],[7]] — 2টা।

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

Python

Python

def combination_sum(candidates, target):
    candidates.sort()                 # sorted: prune-এ break বৈধ হয়
    out = []
    def go(start, path, remaining):
        if remaining == 0:            # base case: যোগফল ঠিক target
            out.append(path[:])       # snapshot!
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                 # PRUNE: পরের সবগুলোও বড় (sorted)
            path.append(candidates[i])             # CHOOSE
            go(i, path, remaining - candidates[i]) # EXPLORE (i: reuse allowed)
            path.pop()                             # UN-CHOOSE
    go(0, [], target)
    return out

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

# ---- tests ----
assert norm(combination_sum([2, 3, 6, 7], 7)) == norm([[2, 2, 3], [7]])
assert norm(combination_sum([2, 3, 5], 8)) == norm(
    [[2, 2, 2, 2], [2, 3, 3], [3, 5]])
assert combination_sum([2], 1) == []            # 1 বানানো অসম্ভব
assert combination_sum([1], 2) == [[1, 1]]      # reuse: 1+1
assert len(combination_sum([2, 3, 6, 7], 7)) == 2
assert combination_sum([8], 7) == []            # candidate > target
print("সব test pass!")

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

• candidates.sort() — sorted হলে break-prune বৈধ হয়।
• if remaining == 0: — base case: যোগফল ঠিক target হয়ে গেছে।
• out.append(path[:]) — snapshot; live path পরে বদলাবে।
• for i in range(start, ...) — start থেকে বলে duplicate সংগ্রহ আসে না।
• if candidates[i] > remaining: break — PRUNE: এটা বড় হলে পরেরগুলোও বড়, পুরো লেজ কাটো।
• go(i, path, remaining - candidates[i]) — EXPLORE: i (i+1 নয়) মানে একই সংখ্যা আবার নেওয়া যায় (reuse)।
• path.pop() — UN-CHOOSE: undo।

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

combination_sum([2,3,6,7],7): 2-এর শাখা গভীরে গিয়ে [2,2,3] (যোগ 7) record করে; [2,2,2]-এ remaining 1, সবচেয়ে ছোট 2-ও বড় → break, dead end; root-এর 7-শাখা [7] দেয়; 6 কখনো কাজে লাগে না। ফল 2টা সংগ্রহ। order গুরুত্বহীন, তাই norm-এ sorted-of-sorted তুলনা — assert stable। অসম্ভব target-এ [], reuse-এ [1,1]। সব মিলে print: সব test pass!।

JavaScript ও test cases

JavaScript

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b);     // sorted: prune-এ break বৈধ হয়
  const out = [];
  const go = (start, path, remaining) => {
    if (remaining === 0) {              // base case: যোগফল ঠিক target
      out.push([...path]);             // snapshot!
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break;   // PRUNE: পরের সবগুলোও বড় (sorted)
      path.push(candidates[i]);                       // CHOOSE
      go(i, path, remaining - candidates[i]);         // EXPLORE (i: reuse allowed)
      path.pop();                                     // UN-CHOOSE
    }
  };
  go(0, [], target);
  return out;
}

// ---- order-independent তুলনার helper ----
const norm = (lol) => JSON.stringify(lol.map(s => [...s].sort((a, b) => a - b)).sort((a, b) => JSON.stringify(a).localeCompare(JSON.stringify(b))));

// ---- test cases ----
assert(norm(combinationSum([2, 3, 6, 7], 7)) === norm([[2, 2, 3], [7]]), "main");
assert(norm(combinationSum([2, 3, 5], 8)) === norm([[2, 2, 2, 2], [2, 3, 3], [3, 5]]), "ex2");
assert(JSON.stringify(combinationSum([2], 1)) === JSON.stringify([]), "অসম্ভব");
assert(norm(combinationSum([1], 2)) === norm([[1, 1]]), "reuse 1+1");
assert(combinationSum([2, 3, 6, 7], 7).length === 2, "count");
assert(JSON.stringify(combinationSum([8], 7)) === JSON.stringify([]), "candidate > target");
console.log("সব JS test pass!");

JS টীকা: তিনটা চাবি এক জায়গায় — start index duplicate সংগ্রহ ঠেকায়, go(i, ...) (i+1 নয়) একই সংখ্যা reuse-এর অনুমতি দেয়, আর sorted candidate-এ candidates[i] > remaining হলে break পুরো hopeless লেজ এক কোপে কাটে। candidates.sort((a, b) => a - b) দিতেই হবে — JS default sort সংখ্যাকে string ধরে, যা prune ভেঙে দিত। remaining integer কমিয়ে target-কেই recursion-এর state বানাই।

TypeScript ও test cases

TypeScript

function combinationSum(candidates: number[], target: number): number[][] {
  candidates.sort((a, b) => a - b);
  const out: number[][] = [];
  const go = (start: number, path: number[], remaining: number): void => {
    if (remaining === 0) {
      out.push([...path]);
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break;          // PRUNE
      path.push(candidates[i]);                       // CHOOSE
      go(i, path, remaining - candidates[i]);         // EXPLORE (reuse)
      path.pop();                                     // UN-CHOOSE
    }
  };
  go(0, [], target);
  return out;
}

function expect<T>(a: T, e: T, m = ""): void { if (a !== e) throw new Error(`FAIL ${m}`); }
const norm = (lol: number[][]): string =>
  JSON.stringify(lol.map(s => [...s].sort((a, b) => a - b))
    .sort((a, b) => JSON.stringify(a).localeCompare(JSON.stringify(b))));

expect(norm(combinationSum([2, 3, 6, 7], 7)), norm([[2, 2, 3], [7]]), "main");
expect(norm(combinationSum([2, 3, 5], 8)), norm([[2, 2, 2, 2], [2, 3, 3], [3, 5]]), "ex2");
expect(JSON.stringify(combinationSum([2], 1)), JSON.stringify([]), "impossible");
expect(norm(combinationSum([1], 2)), norm([[1, 1]]), "reuse");
console.log("সব TS test pass!");

TS টীকা: go-এর তিন প্যারামিটার start: number, path: number[], remaining: number স্পষ্টভাবে recursion-এর state বোঝায় — remaining হলো সঙ্কুচিত-হতে-থাকা target। return type number[][] বলে output সংগ্রহের collection। remaining-কে integer রাখায় base (=== 0) আর prune (> remaining) দুটোই এক সংখ্যা দেখেই হয়, পুরো path যোগ করতে হয় না — টাইপ এটা compile-time-এ পরিষ্কার রাখে।

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

সময়

worst case প্রায় O(n^(target/min)) · (গভীরতা) — গাছের শাখা reuse-এ অনেক, কিন্তু sorted-break বাস্তবে বিশাল pruning দেয়। সহজ ভাষায়: বৈধ সংগ্রহ-সংখ্যার সাথে আনুপাতিক, প্রতিটা গড়তে গভীরতা পর্যন্ত copy।

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

Output বাদ দিলে O(target / min_candidate) — সবচেয়ে গভীর শাখা (সব ছোট সংখ্যা নিলে) এই গভীরতায় যায়, call stack + path। Output ধরলে সব সংগ্রহের মোট আকার।

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

• go(i, ...)-এর বদলে go(i+1, ...) — reuse বন্ধ হয়ে যায়, [2,2,3]-এর মতো পুনরাবৃত্তি আসে না।
• start না দিয়ে প্রতিবার শুরু থেকে loop — একই সংগ্রহ ভিন্ন order-এ বারবার ([2,3] ও [3,2])।
• sort না করে break ব্যবহার — তখন break বৈধ নয় (পরে ছোট candidate থাকতে পারে); হয় sort করো, নয় break-এর বদলে continue।
• base case remaining < 0 চেক না করা ও prune না দেওয়া — তখন target ছাড়িয়েও গভীরে নামে, অপচয়।

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

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

ভিত্তি: Combinations (এই tracker-এর #11)-এর start-index + ../../05-hashing/-এর complement-thinking (remaining target)। ../patterns.md-এর Pattern 5 (Combinations with pruning) এই note-এর সরাসরি উৎস — সেখানকার worked example এই problem-ই। এটা tracker-এর চারটা canonical interview shape-এর একটা — এখানে সবচেয়ে বেশি সময় দাও।

পরের অনুশীলন

• Combination Sum II (each used once + sort-skip) — https://leetcode.com/problems/combination-sum-ii/ (এই tracker-এর #13)
• Combinations (fixed size, reuse নেই) — https://leetcode.com/problems/combinations/ (#11)
• Coin Change (count/min — memoization → DP) — https://leetcode.com/problems/coin-change/ (../../12-dynamic-programming/)

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

Combinations with pruning: start-index + reuse (go(i)) + running remaining complement, sorted candidate-এ candidate > remaining হলে break — listing-সব-সংগ্রহ problem-এর কঙ্কাল; এর "count/min" রূপ (যেমন Coin Change) overlapping subproblem পায়, তখন memoize করে ../../12-dynamic-programming/-এ পৌঁছে যায়।

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

ভবিষ্যতের আমাকে: "Combination Sum = start-index + go(i) (reuse) + remaining target; sort করে > remaining হলে break।" যখনই 'target-এ পৌঁছানো combination, সংখ্যা বারবার চলবে' শুনবে — এই pruned start-index skeleton মনে করবে। আর 'কয়টা উপায়/সর্বনিম্ন কয়টা' হলে — থামো, ওটা memoization → DP।

কোথায় কাজে লাগে

• Coin change / making amount: নির্দিষ্ট দাম মেটানোর সব সংমিশ্রণ (reuse সহ) বের করা।
• Budget allocation: নির্দিষ্ট মোট খরচে পৌঁছানোর সব item-combination।
• Recipe/portion planning: নির্দিষ্ট ক্যালরি/পরিমাণে পৌঁছাতে উপাদানের সংমিশ্রণ।
• Resource provisioning: নির্দিষ্ট capacity পূরণে reusable resource-unit-এর সংমিশ্রণ।
• DP-র সেতু: এর "কয়টা উপায়/সর্বনিম্ন কয়টা" রূপ (Coin Change) overlapping subproblem পায় → memoization → DP।

এক কথায়, "target-এ পৌঁছানো সব combination, সংখ্যা বারবার চলবে" শুনলেই — start-index + reuse + remaining-target + sorted-break এই pruned skeleton; আর "কয়টা/সর্বনিম্ন" চাইলে থেমে DP ভাবো।

---

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