{"id":2834,"date":"2024-03-25T07:39:58","date_gmt":"2024-03-25T07:39:58","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2834"},"modified":"2025-04-07T11:29:24","modified_gmt":"2025-04-07T11:29:24","slug":"coin-change-ii","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/coin-change-ii\/","title":{"rendered":"Coin Change II Problem (C++, Java, Python)"},"content":{"rendered":"\n<p>Money is the most essential thing that we deal with every day. Isn\u2019t it interesting that we have so many denominations of money and can use them in different combinations to pay a certain amount? In this article, we will explore one very famous <a href=\"https:\/\/favtutor.com\/blogs\/dynamic-programming\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">dynamic programming<\/a>-based problem: Coin Change II. We will explore different solutions, from the brute force approach to the most optimal one.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Coin Change II Problem Statement<\/strong><\/h2>\n\n\n\n<p><strong>In the Coin Change II problem, we are given different denominations of money, like 1, 2, 5, 10, etc. We are given a total amount we need to form using combinations of these coins. We need to find the total number of possible combinations. <\/strong><\/p>\n\n\n\n<p>Let\u2019s understand it better with an example:<\/p>\n\n\n\n<p><strong>Input:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background has-link-color has-medium-font-size wp-elements-70e034b242ea842f63ba7787b81bd71b\" style=\"background-color:#fedcba\"><code><strong>coins:<\/strong> &#91; 1, 2, 3 ]\n<strong>amount:<\/strong> 5<\/code><\/pre>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background has-link-color has-medium-font-size wp-elements-074a2c91098b367cd8fa3f762a985f02\" style=\"background-color:#fedcba\"><code>5<\/code><\/pre>\n\n\n\n<p><strong>Explanation:<\/strong><\/p>\n\n\n\n<p>The 5 different possible combinations are:<\/p>\n\n\n\n<p>5 = 3 + 2<\/p>\n\n\n\n<p>5 = 3 + 1 + 1<\/p>\n\n\n\n<p>5 = 2 + 2 + 1<\/p>\n\n\n\n<p>5 = 2 + 1 + 1 + 1&nbsp;<\/p>\n\n\n\n<p>5 = 1 + 1 + 1 + 1 + 1<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/OTYYtSuflbDFLFZmdM63_sARoxDTP2ueFPODPgKKHB1DfL9QCp-vI-CGSN94aYdevLiCJmy9YBREiLmiYDXLZj6OjGFBcfRQeLWM8yWSy-dVY9FKZ526Gd5RxiPPPOMeP7TRuOUSOqx7nlU27AHhupU\" alt=\"Example\"\/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Brute Force Approach: Using Recursion<\/strong><\/h2>\n\n\n\n<p><strong>The most basic solution is to find all the possible combinations and add the ones where the sum is equal to the amount. We can use <a href=\"https:\/\/favtutor.com\/blogs\/recursion-cpp\">recursion<\/a> to explore all the possible combinations.<\/strong> The following steps need to be followed:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We will iterate over the coin array, and at each index, we have two options to either take that coin or ignore that coin.<\/li>\n\n\n\n<li>Take a variable index, which we will use to iterate over the coins array, and initialize it to 0.<\/li>\n\n\n\n<li>Write a recursive function such that, if we take the current coin, we will subtract its value from the total amount; else if we ignore it, the amount will remain the same.<\/li>\n\n\n\n<li>The base case of the recursion will be if we have left with amount = 0, i.e., the combination is found, we can simply return 1 to add it to the answer, else if the coins array is traversed completely, return 0.<\/li>\n\n\n\n<li>If we can take this coin, subtract the amount, and call for the remaining amount by passing the same index, we can infinitely take a coin.<\/li>\n\n\n\n<li>If we skip this coin, increment the index and call the function again for the same amount.<\/li>\n\n\n\n<li>Add the answer returned from both the recursion calls, and return it.<\/li>\n<\/ul>\n\n\n\n<p>The time complexity for this solution will be O(2^(n*amount)) since we are exploring all the combinations using recursion.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Memoization Approach<\/strong><\/h2>\n\n\n\n<p>We can improve the time complexity of the recursive solution by using the concept of memoization.<strong> We can make use of dynamic programming to store the results and reuse them for overlapping problems.<\/strong> If we have calculated the possible combinations of a certain amount, we do not need to calculate again whenever we get the same amount remaining.<\/p>\n\n\n\n<p>Dynamic programming can be applied through these easy steps:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Write the same recursive function and use the below steps to apply memoization to it.<\/li>\n\n\n\n<li>Create a 2d dp array of size n x ( amount + 1 ) to store the results of the sub-problems.<\/li>\n\n\n\n<li>Initialize the dp array to -1; as for the combinations not possible the answer will be -1.<\/li>\n\n\n\n<li>Before calculating again for a certain amount, we will first check it in our dp array ( dp[index][amount] ); if we have calculated it before, we can simply use it.\u00a0<\/li>\n\n\n\n<li>Else, calculate the answer and set dp[index][amount] = answer, so that we can use it again for the sub-problems.<\/li>\n<\/ul>\n\n\n\n<p>The time complexity for this solution will be O(n * amount), where n is the number of coins. There are at max n * amount number of possible combinations, so if we explore them all, the time complexity will be O(n*amount).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Tabulation Approach<\/strong><\/h2>\n\n\n\n<p>The tabulation approach is nothing but a bottom-up version of the above memoization approach. Earlier we were starting from index 0 and amount. Now, we will begin with the amount as 0 and try to reach the solution.<\/p>\n\n\n\n<p>The following steps are required to be followed in the solution:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Create a 2d dp array with size n x ( amount + 1 ).<\/li>\n\n\n\n<li>If amount = 0, there is only one possible combination, so initialize dp[0][0] as 1.<\/li>\n\n\n\n<li>Use a loop from 1 to n to iterate over the row of the dp array and find the solution for each index.<\/li>\n\n\n\n<li>Use a nested loop to iterate over the amount, i.e., from 0 to amount.<\/li>\n\n\n\n<li>If we take a current coin, add the dp[i][amount &#8211; coins[i-1]] since the value of that coin gets subtracted from the amount.<\/li>\n\n\n\n<li>Otherwise, if we didn\u2019t take that coin, we can simply add dp[i-1][amount].<\/li>\n\n\n\n<li>Return the dp[n][amount], which contains the total number of possible combinations that can make the sum = amount<\/li>\n<\/ul>\n\n\n\n<p>The time complexity for this solution will be O(n * amount), where n is the number of coins. We are using two nested loops, one from 1 to n and the other from 0 to amount. That\u2019s why time complexity is O(n*amount).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Optimal Approach: Tabulation + Space Optimization<\/strong><\/h2>\n\n\n\n<p>As we have seen in the above approaches, we have significantly reduced the time complexity, but space is still an issue for us. To reduce the space complexity, we need to optimize our tabulation solution.<\/p>\n\n\n\n<p>We can observe that the answer for any sub-problem depends on two things, dp[i-1][amount] and dp[i][amount &#8211; coins[i] ], i.e., our answer depends on just the current and previous row. S,o instead of storing answers for each point, we can store just the current and previous rows. This will eventually bring the complexity down to O(2*amount).<\/p>\n\n\n\n<p>The following modifications are needed to be done in the tabulation solution:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Use two arrays, i.e., current and previous of size = ( amount + 1 ), instead of a 2d dp array.<\/li>\n\n\n\n<li>The current[amount &#8211; coins[i]] represents our dp[i][amount &#8211; coins[I] ], and the previous[amount] represents our dp[i-1][amount].<\/li>\n\n\n\n<li>Initialize the current vector inside the loop 0 to amount so that we can calculate its values for each amount.<\/li>\n\n\n\n<li>Update the previous = current once the calculations are performed, as the current row becomes the previous when we move to the next row.<\/li>\n\n\n\n<li>Finally, return the answer as the previous[amount], which is nothing but equal to dp[n][amount].<\/li>\n<\/ul>\n\n\n\n<p>Let\u2019s take our example and understand the steps:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/uI_0qtIg9qoi86hkUKQf2UPr6JDTB0qaJaf-H7ZpPA4goM9zKM_am9R2qivjOtSfsQ4Y8CwL4IOosr2G3SEH23r0P8je4VS0-b_ZQzOZTj1OMT0s9gR0VocaN1xHpAgRfT96sPP0HWa5J0w1z8KwfNw\" alt=\"Input\"\/><\/figure>\n\n\n\n<p>Initialize the current and previous vectors:<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/RiQ-1544AfVC4No6QdrHgKo3KMv04d-P9EVPv_fvJciOtil6ZvWvLuqBwI2kSXy5wUlVZcJJF7QrtVa_Y5C3iSjByB9hhaO2DoypkshtVvkqizEUn29aHs1BSAiMEOT0kvg-Vydp5S499APYzRuAQ98\" alt=\"current and previous vectors\"\/><\/figure>\n\n\n\n<p><strong>Iteration: 1 <\/strong>Index = 1<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/fn9q4pMfPzqY077yS4RYYKMyN42Dm4K3F3eN5-6NcTHX3ygeknhsYdXwjftCsDhjxqOlTx1RsB7rN859UUE3RoZD3bMXc1TmWsxEEeBQnDehCkTP0w1wlX79fvUWVenOL8JxF2vByreQ7A6DdMKWoeg\" alt=\"Iteration: 1\"\/><\/figure>\n\n\n\n<p><strong>Iteration: 2 <\/strong>Index = 2<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/BwokHQxSjDpvZYRWzSEwpzOzfbX9YHv-QdVkotTGLzZt3lyjScJyEsawrWmMHM0m73DJe0W-CNuHIlpK13uVXLHE3PtH0vjM57z3-6bLhmqgOAjjeOihujr3KEBSc7VdtYhy71b0vvP2KpPBVMdii-g\" alt=\"Iteration: 2\"\/><\/figure>\n\n\n\n<p>The answer is previous[amount], i.e. 5<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/lh7-us.googleusercontent.com\/oZubQqDHxEtftg7Iv_rJoJI3xjEtGxAMF-ofk5kdDpMAYxmyDJ9njTxT0wXkYiGSDubJKuiVLI9JLBe_PKLB5dl2ijni4a8J_-ZxcWsNLajN_ZzXX_h4RNuoI0-DsLbbGzb0oeAa25yL3_j7ebZD8OA\" alt=\"Answer\"\/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Here is the C++ Solution for the Coin Change II Problem:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint main() {\n    \/\/ Input\n    vector&lt;int&gt; coins = {1, 2, 3};\n    int amount = 5;\n    int n = coins.size(); \n\n    \/\/ Initialize the previous vector\n    vector&lt;long&gt; previous(amount + 1, 0);\n\n    \/\/ Initialize base condition\n    for (int i = 0; i &lt;= amount; i++) {\n        if (i % coins[0] == 0)\n            previous[i] = 1;\n    }\n\n    for (int i = 1; i &lt; n; i++) {\n        \/\/ Initialize the current vector\n        vector&lt;long&gt; current(amount + 1, 0);\n        \n        for (int targetAmount = 0; targetAmount &lt;= amount; targetAmount++) {\n            \/\/ If we ignore the current coin\n            long ans1 = previous[targetAmount]; \n            \n            \/\/ If we take the current coin\n            long ans2 = 0;\n            if (coins[i] &lt;= targetAmount)\n                ans2 = current[targetAmount - coins[i]];\n        \n            \/\/ Answer will be sum of both        \n            current[targetAmount] = ans1 + ans2;\n        }\n        \n        \/\/ Since current row now become previous\n        previous = current;\n    }\n\n    cout &lt;&lt; &quot;Number of possible combinations are: &quot; &lt;&lt; previous[amount];\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>Let&#8217;s implement it in Java:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.Arrays;\n\npublic class CoinChange {\n    public static void main(String[] args) {\n        \/\/ Input\n        int[] coins = {1, 2, 3};\n        int amount = 5;\n        int n = coins.length;\n\n        \/\/ Initialize the previous array\n        long[] previous = new long[amount + 1];\n        Arrays.fill(previous, 0);\n        \n        \/\/ Initialize base condition\n        for (int i = 0; i &lt;= amount; i++) {\n            if (i % coins[0] == 0)\n                previous[i] = 1;\n        }\n\n        \/\/ Loop through each coin\n        for (int i = 1; i &lt; n; i++) {\n            \/\/ Initialize the current array\n            long[] current = new long[amount + 1];\n            Arrays.fill(current, 0);\n\n            \/\/ Loop through each possible amount\n            for (int targetAmount = 0; targetAmount &lt;= amount; targetAmount++) {\n                \/\/ If we ignore the current coin\n                long ans1 = previous[targetAmount];\n                \n                \/\/ If we take the current coin\n                long ans2 = 0;\n                if (coins[i] &lt;= targetAmount)\n                    ans2 = current[targetAmount - coins[i]];\n                \n                \/\/ Answer will be sum of both\n                current[targetAmount] = ans1 + ans2;\n            }\n\n            \/\/ Update previous array with current array\n            previous = current;\n        }\n\n        System.out.println(&quot;Number of possible combinations are: &quot; + previous[amount]);\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>Here is the Python code for the Coin Change II Problem:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">def main():\n    # Input\n    coins = [1, 2, 3]\n    amount = 5\n    n = len(coins)\n\n    # Initialize the previous array\n    previous = [0] * (amount + 1)\n    for i in range(amount + 1):\n        if i % coins[0] == 0:\n            previous[i] = 1\n\n    # Loop through each coin\n    for i in range(1, n):\n        # Initialize the current array\n        current = [0] * (amount + 1)\n\n        # Loop through each possible amount\n        for target_amount in range(amount + 1):\n            # If we ignore the current coin\n            ans1 = previous[target_amount]\n            \n            # If we take the current coin\n            ans2 = 0\n            if coins[i] &lt;= target_amount:\n                ans2 = current[target_amount - coins[i]]\n            \n            # Answer will be sum of both\n            current[target_amount] = ans1 + ans2\n\n        # Update previous array with current array\n        previous = current\n\n    print(&quot;Number of possible combinations are:&quot;, previous[amount])\n\n\nif __name__ == &quot;__main__&quot;:\n    main()<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background has-link-color wp-elements-b8182a58fbc9ae6680773ef2db372f06\" style=\"background-color:#fedcba\"><code>Number of possible combinations are: 5<\/code><\/pre>\n\n\n\n<p>The time complexity for this solution will be O(n * amount), where n is the number of coins. We are using two nested loops, one from 1 to n and the other from 0 to amount. That\u2019s why time complexity is O(n*amount).<\/p>\n\n\n\n<p>The space complexity is O(amount), which is used by the previous and current arrays.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>So, we explore one of the problems involving recursion and dynamic programming. We understood all the approaches to solve the problem of <a href=\"https:\/\/leetcode.com\/problems\/coin-change-ii\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">Coin Change II<\/a>. We were able to reduce the time complexity from exponential to O(n*amount). <\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Money is the most essential thing that we deal with every day. Isn\u2019t it interesting that we have so many denominations of money and can use them in different combinations to pay a certain amount? In this article, we will explore one very famous dynamic programming-based problem: Coin Change II. We will explore different solutions, [&hellip;]<\/p>\n","protected":false},"author":4,"featured_media":2836,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-2834","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2834","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=2834"}],"version-history":[{"count":7,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2834\/revisions"}],"predecessor-version":[{"id":7385,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2834\/revisions\/7385"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2836"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=2834"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=2834"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=2834"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}