012 — Combination Sum

Source

• 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

1. Problem in simple words

আলাদা ধনাত্মক সংখ্যার একটা 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)

2. Which basic idea does this inherit from?

ভিত্তি হলো 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 থেকে আসে — এখনো কতটা যোগফল দরকার।

3. What is the hidden math or logic?

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

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

sort করা [2, 3, 6, 7], target 7; node-এ remaining, prune যখন candidate > remaining:

                       go(0, [], 7)
        2 /              3 |          6,7 (prune later)
   go(0,[2],5)       go(1,[3],4)
   2/  3| ...         3| (6>4 break)
go(0,[2,2],3)    go(1,[3,3],1)
 2| 3(prune>3-no,=3 ok)   3>1 break -> dead
go(0,[2,2,2],1) go(1,[2,2,3],0)=record [2,2,3]
 2>1 break -> dead
... এবং root-এর 7-branch: go(3,[7],0) = record [7]

remaining == 0 -> record; candidate > remaining -> break (sorted)।

8. Example input and 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]]

9. Brute force thinking

প্রথম সরল চিন্তা: যেহেতু 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

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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 লেজ কাটে।

13. Thinking tweak

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

14. Step-by-step dry run

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

15. Python solution

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

16. Line-by-line code explanation

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

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

• 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 ছাড়িয়েও গভীরে নামে, অপচয়।

21. Which basic problem this inherits from

ভিত্তি: 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-এর একটা — এখানে সবচেয়ে বেশি সময় দাও।

22. Similar harder problems

• 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/)

23. Pattern learned

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/-এ পৌঁছে যায়।

24. Final summary

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

25. JavaScript solution (with test cases)

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 বানাই।

26. TypeScript solution (with test cases)

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-এ পরিষ্কার রাখে।

27. কোথায় কাজে লাগে (real-world use)

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