{"id":10222,"date":"2025-10-03T14:22:49","date_gmt":"2025-10-03T08:52:49","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=10222"},"modified":"2025-10-03T14:48:29","modified_gmt":"2025-10-03T09:18:29","slug":"coin-change-ii","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/coin-change-ii\/","title":{"rendered":"Coin Change II"},"content":{"rendered":"\n<!-- PrismJS for Syntax Highlighting -->\n<link href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\" rel=\"stylesheet\">\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #030302;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2 {\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n\n.wp_blog_explanation code {\n  background: #fef9f4;   \/* light bg instead of dark blue *\/\n  color: #E58C32;        \/* brand orange *\/\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n  font-weight: 600;      \/* optional, makes it pop *\/\n}\n\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0, 0, 0, 0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n\n\/* Dark mode variables *\/\n.wp_blog_theme.dark-mode {\n  --light-bg: #121212;\n  --text-dark: #f5f5f5;\n  --shadow: 0 4px 12px rgba(255, 255, 255, 0.08);\n  --code-bg: #1e1e1e;\n  --code-text: #c5f0ff;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_explanation {\n  background: #1e1e1e;\n}\n\n\/* Dark mode code highlight *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation code {\n  background: #333;\n  color: #ffd27f;\n}\n\n.wp_blog_theme {\n  position: relative; \/* makes it the reference for absolute children *\/\n}\n\n.wp_blog_toggle-btn {\n  position: absolute;\n  top: 1rem;\n  right: 1rem;\n  z-index: 9999;\n  padding: 0.5rem 0.8rem;\n  border-radius: 10%;\n  background: var(--primary);\n  color: white;\n  font-weight: bold;\n  cursor: pointer;\n  border: none;\n  box-shadow: var(--shadow);\n  transition: background 0.3s, transform 0.2s;\n}\n\n.wp_blog_toggle-btn:hover {\n  background: #cc772e;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_code-tabs-container {\n  background: #1e1e1e;\n}\n<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\">\n  <button id=\"blogNotesThemeToggle\" class=\"wp_blog_toggle-btn\">\ud83c\udf19<\/button>\n  <h1 class=\"wp_blog_main-heading\"><\/h1>\n\n  <div class=\"wp_blog_explanation\">\n    <h2>Problem Statement:<\/h2>\n    <p>\n       You are given an integer array <code>coins<\/code> representing coins of different denominations and an integer <code>amount<\/code> representing a total amount of money. \n    <\/p>\n\n    <p>\n        Return <i>the number of combinations that make up that amount<\/i>. If that amount of money cannot be made up by any combination of the coins, return <code>0<\/code>.\n    <\/p>\n\n    <p>\n        You may assume that you have an infinite number of each kind of coin.\n    <\/p>\n\n    <p>\n        The answer is <strong>guaranteed<\/strong> to fit into a signed <strong>32-bit<\/strong> integer.\n    <\/p>\n    <h3>Example 1:<\/h2>\n    <p><strong>Input:<\/strong> amount = 5, coins = [1,2,5]<\/p>\n    <p><strong>Output:<\/strong> 4<\/p>\n    <p><strong>Explanation:<\/strong>  there are four ways to make up the amount:\n    <pre>\n        5=5\n        5=2+2+1\n        5=2+1+1+1\n        5=1+1+1+1+1\n    <\/pre>\n    \n    <\/p>\n\n    <h3>Example 2:<\/h2>\n    <p><strong>Input:<\/strong> amount = 3, coins = [2]<\/p>\n    <p><strong>Output:<\/strong> 0<\/p>\n    <p><strong>Explanation:<\/strong> the amount of 3 cannot be made up just with coins of 2.<\/p>\n\n    <h3>Example 3:<\/h2>\n    <p><strong>Input:<\/strong> amount = 10, coins = [10]<\/p>\n    <p><strong>Output:<\/strong> 1<\/p>\n\n    <h3>Constraints<\/h3>\n    <ul>\n       <li><code>1 <= coins.length <= 300<\/code><\/li>\n        <li><code>1 <= coins[i] <= 5000<\/code><\/li>\n        <li>All the values of coins are <strong>unique<\/strong>.<\/li>\n        <li><code>0 <= amount <= 5000<\/code><\/li>\n    <\/ul>\n    \n<h2>Approach:<\/h2>\n<ul>\n    <li><strong>Recursion with Memoization<\/strong>\n    <ul>\n        <li>Define a function <code>fn(remS, start)<\/code> \u2192 number of ways to make <code>remS<\/code> using coins from index <code>start<\/code> onward.<\/li>\n        <li>Use <code>dp[remS][start]<\/code> to cache results and avoid recomputation.<\/li>\n    <\/ul>\n    <\/li>\n\n    <li><strong>Base cases are: <\/strong>\n        <ul>\n            <li>If <code>remS == 0<\/code> \u2192 found 1 valid combination \u2192 return <code>1<\/code>.<\/li>\n            <li>If <code>remS < 0<\/code> \u2192 no valid way \u2192 return <code>0<\/code>.<\/li>\n        <\/ul>\n    <\/li>\n\n    <li>From index <code>start<\/code> to end, try picking each coin:\n        <code>combinations += fn(remS - coins[i], i)   \/\/ i instead of i+1 because coins[i] can be reused<\/code>\n    <\/li>\n\n    <li>At last, Call <code>fn(amount, 0)<\/code> \u2192 total number of unique combinations to make <code>amount<\/code>.<\/li>\n<\/ul>\n\n    <h2>Time & Space Complexity:<\/h2>\n    <p><strong>Time Complexity:<\/strong> <code>O(amount * n)<\/code><\/p>\n    <p><strong>Space Complexity:<\/strong> <code>O(amount * n)<\/code><\/p>\n\n<h2>Dry Run<\/h2>\n<div style=\"background: var(--light-bg); border-left: 4px solid var(--primary); padding: 1rem; border-radius: var(--tab-radius); margin: 1rem 0; color: var(--text-dark);\">\n  <p><strong>Input:<\/strong> <code>amount = 5, coins = [1, 2, 5]<\/code><\/p>\n  <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\">\nInitial:\n n = 3\n dp rows 0..5 \u00d7 cols 0..2 initialized to -1\n\nCall fn(remS = 5, start = 0)\n\nfn(5,0):\n combinations = 0\n i = 0 \u2192 call fn(4,0)\n i = 1 \u2192 call fn(3,1)\n i = 2 \u2192 call fn(0,2)\n\nfn(4,0):\n combinations = 0\n i = 0 \u2192 fn(3,0)\n i = 1 \u2192 fn(2,1)\n i = 2 \u2192 fn(-1,2) = 0\n\n fn(3,0):\n  combinations = 0\n  i = 0 \u2192 fn(2,0)\n  i = 1 \u2192 fn(1,1)\n  i = 2 \u2192 fn(-2,2) = 0\n\n  fn(2,0):\n   combinations = 0\n   i = 0 \u2192 fn(1,0)\n   i = 1 \u2192 fn(0,1) = 1\n   i = 2 \u2192 fn(-3,2) = 0\n\n   fn(1,0):\n    combinations = 0\n    i = 0 \u2192 fn(0,0) = 1\n    i = 1 \u2192 fn(-1,1) = 0\n    i = 2 \u2192 fn(-4,2) = 0\n    \u2192 combinations = 1\n    dp[1][0] = 1\n    return 1\n\n   Back in fn(2,0):\n   - from i=0 got 1 (fn(1,0))\n   - from i=1 got 1 (fn(0,1))\n   \u2192 combinations = 1 + 1 = 2\n   dp[2][0] = 2\n   return 2\n\n  Back in fn(3,0):\n  - from i=0 got 2 (fn(2,0))\n  - fn(1,1) next:\n\n  fn(1,1):\n   i = 1 \u2192 fn(-1,1) = 0\n   i = 2 \u2192 fn(-4,2) = 0\n   \u2192 combinations = 0\n   dp[1][1] = 0\n   return 0\n\n  \u2192 fn(3,0) combinations = 2 + 0 + 0 = 2\n  dp[3][0] = 2\n  return 2\n\n fn(2,1):\n  i = 1 \u2192 fn(0,1) = 1\n  i = 2 \u2192 fn(-3,2) = 0\n  \u2192 combinations = 1\n  dp[2][1] = 1\n  return 1\n\n Back in fn(4,0):\n - from i=0 \u2192 fn(3,0) = 2\n - from i=1 \u2192 fn(2,1) = 1\n - i=2 \u2192 0\n \u2192 combinations = 2 + 1 = 3\n dp[4][0] = 3\n return 3\n\nfn(3,1) (from fn(5,0) i=1):\n check dp[3][1] \u2014 not set\n i=1 \u2192 fn(1,1) = 0 (from earlier)\n i=2 \u2192 fn(-2,2) = 0\n \u2192 combinations = 0\n dp[3][1] = 0\n return 0\n\nfn(0,2) (from fn(5,0) i=2):\n remS === 0 \u2192 return 1\n\nBack in fn(5,0):\n - from i=0 \u2192 fn(4,0) = 3\n - from i=1 \u2192 fn(3,1) = 0\n - from i=2 \u2192 fn(0,2) = 1\n \u2192 combinations = 3 + 0 + 1 = 4\n dp[5][0] = 4\n return 4\n\nSome dp entries filled:\n dp[1][0] = 1\n dp[2][0] = 2\n dp[3][0] = 2\n dp[1][1] = 0\n dp[2][1] = 1\n dp[3][1] = 0\n dp[4][0] = 3\n dp[5][0] = 4\n\nFinal:\n fn(5,0) = 4\n (combinations: [1+1+1+1+1], [1+1+1+2], [1+2+2], [5])\n  <\/pre>\n\n  <p><strong>Output:<\/strong> <code>4<\/code><\/p>\n<\/div>\n\n        <!-- <h2>Visualisation:<\/h2>\n        <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/09\/Screenshot-2025-09-30-at-3.00.03\u202fPM.png\" alt=\"Stocks\" \/>\n    -->\n<\/div>\n\n\n  <div class=\"wp_blog_code-tabs-container\">\n    <div class=\"wp_blog_code-tabs-header\">\n      <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">JavaScript<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n      <pre><code class=\"language-javascript\">\nvar change = function(amount, coins) {\n    let n = coins.length;\n    let dp = Array.from({length: amount + 1}, () => Array(n).fill(-1));\n\n    let fn = (remS, start) => {\n        if(remS === 0) return 1;\n        if(remS < 0) return 0;\n        \n        if(dp[remS][start] != -1) return dp[remS][start];\n\n        let combinations = 0;\n        for(let i=start; i < n; i++){\n            combinations += fn(remS - coins[i], i);\n        }\n        return dp[remS][start] = combinations;\n    }\n    return fn(amount, 0);\n};\n<\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n      <pre><code class=\"language-python\">\ndef change(amount, coins):\n    n = len(coins)\n    if n == 0:\n        return 1 if amount == 0 else 0\n    dp = [[-1] * n for _ in range(amount + 1)]\n    def fn(rem, start):\n        if rem == 0:\n            return 1\n        if rem < 0:\n            return 0\n        if dp[rem][start] != -1:\n            return dp[rem][start]\n        combinations = 0\n        for i in range(start, n):\n            combinations += fn(rem - coins[i], i)\n        dp[rem][start] = combinations\n        return combinations\n    return fn(amount, 0)\n      <\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n      <pre><code class=\"language-java\">\npublic class Solution {\n    public long change(int amount, int[] coins) {\n        int n = coins.length;\n        if (n == 0) return amount == 0 ? 1L : 0L;\n        long[][] dp = new long[amount + 1][n];\n        for (int i = 0; i <= amount; i++) {\n            for (int j = 0; j < n; j++) {\n                dp[i][j] = -1;\n            }\n        }\n        return fn(amount, 0, coins, dp);\n    }\n    private long fn(int rem, int start, int[] coins, long[][] dp) {\n        if (rem == 0) return 1;\n        if (rem < 0) return 0;\n        if (dp[rem][start] != -1) return dp[rem][start];\n\n        long combinations = 0;\n        for (int i = start; i < coins.length; i++) {\n            combinations += fn(rem - coins[i], i, coins, dp);\n        }\n        dp[rem][start] = combinations;\n        return combinations;\n    }\n}\n<\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n      <pre><code class=\"language-cpp\">\n#include &lt;bits\/stdc++.h&gt;     \nusing namespace std;\n\nlong long change_helper(int rem, int start, const vector<int>& coins, vector<vector<long long>>& dp) {\n    if (rem == 0) return 1;\n    if (rem < 0) return 0;\n    if (dp[rem][start] != -1) return dp[rem][start];\n\n    long long combinations = 0;\n    int n = coins.size();\n    for (int i = start; i < n; ++i) {\n        combinations += change_helper(rem - coins[i], i, coins, dp);\n    }\n    dp[rem][start] = combinations;\n    return combinations;\n}\nlong long change(int amount, vector<int>& coins) {\n    int n = coins.size();\n    if (n == 0) return (amount == 0) ? 1 : 0;\n    vector<vector<long long>> dp(amount + 1, vector<long long>(n, -1));\n    return change_helper(amount, 0, coins, dp);\n}\n<\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n      <pre><code class=\"language-c\">\n#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\nlong long fn_helper(int rem, int start, int *coins, int n, long long *dp) {\n    if (rem == 0) return 1;\n    if (rem < 0) return 0;\n    long long idx = (long long)rem * n + start;\n    if (dp[idx] != -1) return dp[idx];\n\n    long long combinations = 0;\n    for (int i = start; i < n; ++i) {\n        combinations += fn_helper(rem - coins[i], i, coins, n, dp);\n    }\n    dp[idx] = combinations;\n    return combinations;\n}\nlong long change(int amount, int *coins, int n) {\n    if (n == 0) return amount == 0 ? 1LL : 0LL;\n    long long total = (long long)(amount + 1) * n;\n    long long *dp = (long long*)malloc(sizeof(long long) * total);\n    if (!dp) return 0; \/\/ out of memory, simple handling\n    for (long long i = 0; i < total; ++i) dp[i] = -1;\n    long long res = fn_helper(amount, 0, coins, n, dp);\n    free(dp);\n    return res;\n}\n <\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n      <pre><code class=\"language-csharp\">\nusing System;\n\npublic class Solution {\n    public long Change(int amount, int[] coins) {\n        int n = coins.Length;\n        if (n == 0) return amount == 0 ? 1L : 0L;\n        long[,] dp = new long[amount + 1, n];\n        for (int i = 0; i <= amount; i++)\n            for (int j = 0; j < n; j++)\n                dp[i, j] = -1;\n\n        long Fn(int rem, int start) {\n            if (rem == 0) return 1;\n            if (rem < 0) return 0;\n            if (dp[rem, start] != -1) return dp[rem, start];\n\n            long combinations = 0;\n            for (int i = start; i < n; i++) {\n                combinations += Fn(rem - coins[i], i);\n            }\n            dp[rem, start] = combinations;\n            return combinations;\n        }\n        return Fn(amount, 0);\n    }\n}\n      <\/code><\/pre>\n    <\/div>\n  <\/div>\n<\/div>\n\n<script>\ndocument.addEventListener(\"DOMContentLoaded\", () => {\n  const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n  const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n  buttons.forEach((button) => {\n    button.addEventListener(\"click\", () => {\n      const lang = button.getAttribute(\"data-lang\");\n\n      buttons.forEach((btn) => btn.classList.remove(\"active\"));\n      contents.forEach((content) => content.classList.remove(\"active\"));\n\n      button.classList.add(\"active\");\n      document\n        .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n        .classList.add(\"active\");\n    });\n  });\n\n  const themeToggle = document.getElementById(\"blogNotesThemeToggle\");\n  const themeContainer = document.querySelector(\".wp_blog_theme\");\n\n  themeToggle.addEventListener(\"click\", () => {\n    themeContainer.classList.toggle(\"dark-mode\");\n    themeToggle.textContent =\n      themeContainer.classList.contains(\"dark-mode\") ? \"\u2600\ufe0f\" : \"\ud83c\udf19\";\n  });\n});\n<\/script>\n`\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Problem Statement: You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0. You may assume<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[210,322,176,175,211,810,174,172,173],"tags":[],"class_list":["post-10222","post","type-post","status-publish","format-standard","category-algorithms","category-algorithms-and-data-structures","category-csharp","category-cplusplus","category-data-structures","category-dsa","category-java","category-javascript","category-python"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10222","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=10222"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10222\/revisions"}],"predecessor-version":[{"id":10223,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10222\/revisions\/10223"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=10222"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=10222"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=10222"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}