{"id":14895,"date":"2022-10-09T13:54:12","date_gmt":"2022-10-09T08:24:12","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/"},"modified":"2022-10-09T13:54:12","modified_gmt":"2022-10-09T08:24:12","slug":"solved-dynamic-programming-cansum-memoization-in-c","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/","title":{"rendered":"[Solved] Dynamic programming &#8211; canSum memoization in C++"},"content":{"rendered":"<p> [ad_1]<br \/>\n<\/p>\n<div id=\"answer-66726177\" class=\"answer js-answer accepted-answer js-accepted-answer\" data-answerid=\"66726177\" data-parentid=\"66721219\" data-score=\"2\" data-position-on-page=\"1\" data-highest-scored=\"1\" data-question-has-accepted-highest-score=\"1\" itemprop=\"acceptedAnswer\" itemscope itemtype=\"https:\/\/schema.org\/Answer\">\n<div class=\"post-layout\">\n<div class=\"votecell post-layout--left\"><\/div>\n<div class=\"answercell post-layout--right\">\n<div class=\"s-prose js-post-body\" itemprop=\"text\">\n<p>The problem in your code is the way you handle the storing of sates in your <code>memo<\/code> table. You store only when the result is desired in the <code>for<\/code> loop and same problem is while returning using the memo table. So, the states which result in false are not stored in your memo until the complete recursive call ends and you are out of the loop. So, your recursion keeps on calculating the same states again and again. Your logic is correct but dynamic programming integration in recursive code is not proper. Your code will give an output, you just need to wait for a long time even for a small input. Below I have explained the above mentioned problems in detail.<\/p>\n<ol>\n<li>\n<p>You return from <code>memo<\/code> only if the result is true i.e. the if condition:<\/p>\n<pre><code>...\nif(memo[remainder] == true)\n    return true;\n...\n<\/code><\/pre>\n<p>is the problem. We use dynamic programming to save the result of a state that has been calculated so that if we come across the same problem in future, we don&#8217;t have to recalculate it and we can return its result from saved <code>memo<\/code> table to avoid going into recursion again. We return the result from <code>memo<\/code> table irrespective of the result. But here you are returning only if the result was true. You should instead use this:<\/p>\n<pre><code>...\nif (memo.find(targetSum)!=memo.end())\n    return memo[targetSum];\n...\n<\/code><\/pre>\n<\/li>\n<li>\n<p>This is also the problem while you are storing the results in the memo table in the for loop. The if condition in the for loop:<\/p>\n<pre><code>for (auto i : vec) {\n    remainder = targetSum - i;\n    if (canSum(remainder, vec, memo)) {\n        memo.emplace(remainder, true);\n        return true;\n    }\n}\n<\/code><\/pre>\n<p>is the problem. We store the result in the <code>memo<\/code> table irrespective of our desired result.<\/p>\n<\/li>\n<\/ol>\n<p>Here is the complete code with both problems fixed.<\/p>\n<pre><code>#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;map&gt;\n\nusing namespace std;\n\nbool canSum(int targetSum, vector&lt;int&gt; &amp;vec, map&lt;int, bool&gt; &amp;memo) {\n    int remainder;\n    if (memo.find(targetSum)!=memo.end())\n        return memo[targetSum];\n    else if (targetSum == 0)\n        return true;\n    else if (targetSum &lt; 0)\n        return false;\n    else{\n        bool ans = false;\n        for (auto i : vec) {\n            remainder = targetSum - i;\n            ans = ans || canSum(remainder, vec, memo);\n            if (ans) {\n                memo.emplace(targetSum, true);\n                return true;\n            }\n        }\n        memo.emplace(targetSum, false);\n    }\n    return false;\n}\n\nint main() {\n    vector&lt;int&gt; vector1{7, 14};\n    int sum = 300;\n    map&lt;int, bool&gt; memo;\n    if (canSum(sum, vector1, memo))\n        cout &lt;&lt; \"true\";\n    else\n        cout &lt;&lt; \"false\";\n}\n<\/code><\/pre>\n<p>This is the answer to your question &#8220;I do not know why <code>canSum<\/code> is not returning anything.&#8221;<\/p>\n<p>Now, in general one should not use recursive DP as it is too much time consuming and iterative DP is best suited for competitive programming problems.<\/p>\n<\/p><\/div>\n<div class=\"mt24\"><\/div>\n<\/div>\n<p>            <span class=\"d-none\" itemprop=\"commentCount\">5<\/span> <\/p><\/div>\n<\/div>\n<p>[ad_2]<\/p>\n<p>solved Dynamic programming &#8211; canSum memoization in C++ <\/p>\n","protected":false},"excerpt":{"rendered":"<p>[ad_1] The problem in your code is the way you handle the storing of sates in your memo table. You store only when the result is desired in the for loop and same problem is while returning using the memo table. So, the states which result in false are not stored in your memo until &#8230; <a title=\"[Solved] Dynamic programming &#8211; canSum memoization in C++\" class=\"read-more\" href=\"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/\" aria-label=\"More on [Solved] Dynamic programming &#8211; canSum memoization in C++\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[324,1372],"class_list":["post-14895","post","type-post","status-publish","format-standard","hentry","category-solved","tag-c","tag-dynamic-programming"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.5 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>[Solved] Dynamic programming - canSum memoization in C++ - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] Dynamic programming - canSum memoization in C++ - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] The problem in your code is the way you handle the storing of sates in your memo table. You store only when the result is desired in the for loop and same problem is while returning using the memo table. So, the states which result in false are not stored in your memo until ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-10-09T08:24:12+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] Dynamic programming &#8211; canSum memoization in C++\",\"datePublished\":\"2022-10-09T08:24:12+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/\"},\"wordCount\":321,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"c++\",\"dynamic-programming\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/\",\"name\":\"[Solved] Dynamic programming - canSum memoization in C++ - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-10-09T08:24:12+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] Dynamic programming &#8211; canSum memoization in C++\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] Dynamic programming - canSum memoization in C++ - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] Dynamic programming - canSum memoization in C++ - JassWeb","og_description":"[ad_1] The problem in your code is the way you handle the storing of sates in your memo table. You store only when the result is desired in the for loop and same problem is while returning using the memo table. So, the states which result in false are not stored in your memo until ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/","og_site_name":"JassWeb","article_published_time":"2022-10-09T08:24:12+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] Dynamic programming &#8211; canSum memoization in C++","datePublished":"2022-10-09T08:24:12+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/"},"wordCount":321,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["c++","dynamic-programming"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/","url":"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/","name":"[Solved] Dynamic programming - canSum memoization in C++ - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-10-09T08:24:12+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-dynamic-programming-cansum-memoization-in-c\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] Dynamic programming &#8211; canSum memoization in C++"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/14895","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=14895"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/14895\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=14895"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=14895"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=14895"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}