Recursion and Backtracking — Problem Tracker¶
এই folder-এর practice ledger, easy → hard সাজানো। Recursion এমন একটা skill যেটা শুধু code করে না, এঁকে তৈরি হয়: এখানকার প্রতিটা problem-এর জন্য, code লেখার আগে আর পরে কাগজে recursion tree বা choose/explore/un-choose trace-টা sketch করো। একটা solve করলে তার Status বদলাও আর ../../templates/ds-problem-note-template.md-র 24-section template দিয়ে reserved Note file-এ একটা পুরো note লেখো। "Inherits from" column বলে দেয় প্রতিটা problem আগের কোন idea থেকে গজিয়েছে — কোনো problem অসম্ভব মনে হলে আগে গিয়ে তার parent-টা আবার solve করো।
Problem-গুলো শুধু official link দিয়ে reference করা; নিজের note-এ প্রতিটা task নিজের ভাষায় লেখো।
| # | Problem | Difficulty | Source | Pattern | Inherits from | Note file | Status |
|---|---|---|---|---|---|---|---|
| 1 | Fibonacci Number — https://leetcode.com/problems/fibonacci-number/ | Easy | LeetCode | Decrease-and-conquer → memoization | Loops; recursion tree-র ছবি | 001-fibonacci-number.md | planned |
| 2 | Climbing Stairs — https://leetcode.com/problems/climbing-stairs/ | Easy | LeetCode | Decrease-and-conquer → memoization | ছদ্মবেশে Fibonacci | 002-climbing-stairs.md | planned |
| 3 | Reverse String — https://leetcode.com/problems/reverse-string/ | Easy | LeetCode | Decrease-and-conquer (two ends) | Swap + ভেতরের দিকে recurse | 003-reverse-string.md | planned |
| 4 | Power of Two — https://leetcode.com/problems/power-of-two/ | Easy | LeetCode | Decrease-and-conquer (halving) | Divisibility (math fundamentals) | 004-power-of-two.md | planned |
| 5 | Pow(x, n) — https://leetcode.com/problems/powx-n/ | Medium | LeetCode | Divide-and-conquer | concept.md-র fast power | 005-pow-x-n.md | planned |
| 6 | Merge Two Sorted Lists — https://leetcode.com/problems/merge-two-sorted-lists/ | Easy | LeetCode | Decrease-and-conquer on lists | Linked lists section + leap of faith | 006-merge-two-sorted-lists.md | planned |
| 7 | Subsets — https://leetcode.com/problems/subsets/ | Medium | LeetCode | Include/exclude branch | Decrease-and-conquer, এবার branching সহ | 007-subsets.md | planned |
| 8 | Letter Combinations of a Phone Number — https://leetcode.com/problems/letter-combinations-of-a-phone-number/ | Medium | LeetCode | Cartesian choose-explore | Subsets branching, k-way | 008-letter-combinations-phone.md | planned |
| 9 | Permutations — https://leetcode.com/problems/permutations/ | Medium | LeetCode | Choose each remaining | Subsets + seen-set (../../05-hashing/) | 009-permutations.md | planned |
| 10 | Subsets II — https://leetcode.com/problems/subsets-ii/ | Medium | LeetCode | Include/exclude + duplicate skip | Subsets + sort-and-skip | 010-subsets-ii.md | planned |
| 11 | Combinations — https://leetcode.com/problems/combinations/ | Medium | LeetCode | Start-index combinations | Fixed size k সহ subsets | 011-combinations.md | planned |
| 12 | Combination Sum — https://leetcode.com/problems/combination-sum/ | Medium | LeetCode | Combinations with pruning | Combinations + remaining-target complement | 012-combination-sum.md | planned |
| 13 | Combination Sum II — https://leetcode.com/problems/combination-sum-ii/ | Medium | LeetCode | Pruning + duplicate handling | Combination Sum + Subsets II-র skip trick | 013-combination-sum-ii.md | planned |
| 14 | Permutations II — https://leetcode.com/problems/permutations-ii/ | Medium | LeetCode | Choose remaining + duplicate skip | Permutations + sorted skip | 014-permutations-ii.md | planned |
| 15 | Generate Parentheses — https://leetcode.com/problems/generate-parentheses/ | Medium | LeetCode | Constraint backtracking (open/close counts) | Subsets branching + validity pruning | 015-generate-parentheses.md | planned |
| 16 | Palindrome Partitioning — https://leetcode.com/problems/palindrome-partitioning/ | Medium | LeetCode | Cut-point backtracking | Combinations (cut position-গুলোই choice) | 016-palindrome-partitioning.md | planned |
| 17 | Word Search — https://leetcode.com/problems/word-search/ | Medium | LeetCode | Grid backtracking, visited marks | Constraint backtracking + cell-এ seen-set | 017-word-search.md | planned |
| 18 | Creating Strings — https://cses.fi/problemset/ (CSES, task name: Creating Strings) | Medium | CSES | Permutations with duplicates | CP-গতিতে Permutations II | 018-cses-creating-strings.md | planned |
| 19 | N-Queens — https://leetcode.com/problems/n-queens/ | Hard | LeetCode | Constraint backtracking | Permutations + তিনটা blocked-line set | 019-n-queens.md | planned |
| 20 | N-Queens II — https://leetcode.com/problems/n-queens-ii/ | Hard | LeetCode | Constraint backtracking (count only) | N-Queens, board-গুলো বাদ দাও | 020-n-queens-ii.md | planned |
| 21 | Chessboard and Queens — https://cses.fi/problemset/ (CSES, task name: Chessboard and Queens) | Hard | CSES | N-Queens with blocked cells | N-Queens + বাড়তি constraint | 021-cses-chessboard-and-queens.md | planned |
| 22 | Sudoku Solver — https://leetcode.com/problems/sudoku-solver/ | Hard | LeetCode | Constraint backtracking | N-Queens-এর শৃঙ্খলা, প্রতি cell-এ 3টা unit-set | 022-sudoku-solver.md | planned |
| 23 | Word Search II — https://leetcode.com/problems/word-search-ii/ | Hard | LeetCode | Backtracking + trie preview | Word Search; trie আসবে পরের এক section-এ | 023-word-search-ii.md | planned |
এই tracker কীভাবে ব্যবহার করবে¶
- Status-গুলো:
planned→attempted→solved→revisit(এক সপ্তাহ পরে cold অবস্থায় আবার solve করেছ)। - প্রতিটা backtracking problem-এর note-এ থাকতেই হবে: (a) প্রতি level-এ decision-টা কী, (b) কী choose/un-choose হচ্ছে, (c) pruning condition-টা কী। এই তিনটার নাম বলতে না পারলে তুমি শেখোনি, solution copy করেছ।
- Problem 7, 9, 12, আর 19 হলো চারটা canonical interview shape — ওই note-গুলোতে সবচেয়ে বেশি invest করো।
- 1-2 শেষ করার পরপরই
@lru_cacheদিয়ে আবার করো আর call-count-এর পার্থক্যটা লিখে রাখো; ওই observation-টাই../../12-dynamic-programming/-এর entry ticket। - পুরো note format:
../../templates/ds-problem-note-template.md-র 24-section template।