{"id":2501,"date":"2021-10-09T11:19:00","date_gmt":"2021-10-09T05:49:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2501"},"modified":"2022-06-15T11:50:18","modified_gmt":"2022-06-15T06:20:18","slug":"subset-sum-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/subset-sum-problem\/","title":{"rendered":"Subset Sum Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#recursive-approach\">Recursive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-of-recursive-approach\">C Implementation Of Recursive Approach<\/a><\/li><li><a href=\"#-java-implementation-of-recursive-approach\"><meta charset=\"utf-8\">Java Implementation Of Recursive Approach<\/a><\/li><li><a href=\"#-python-implementation-of-recursive-approach\"><meta charset=\"utf-8\">Python Implementation Of Recursive Approach<\/a><\/li><\/ul><li><a href=\"#dynamic-programming-approach\">Dynamic Programming Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-for-subset-sum\">C Implementation For Subset Sum<\/a><\/li><li><a href=\"#-java-implementation-for-subset-sum\"><meta charset=\"utf-8\">Java Implementation For Subset Sum<\/a><\/li><li><a href=\"#-python-implementation-for-subset-sum\"><meta charset=\"utf-8\">Python Implementation For Subset Sum<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given an array of non-negative integers and an integer sum. We have to tell whether there exists any subset in an array whose sum is equal to the given integer sum.<\/p>\n\n\n\n<p>Examples:<\/p>\n\n\n\n<p><strong>Input:<\/strong> arr[] = {3, 34, 4, 12, 3, 2}, sum = 7<br><strong>Output:<\/strong> True<br><strong>Explanation:<\/strong> There is a subset (4, 3) with sum 7.<\/p>\n\n\n\n<p><strong>Input:<\/strong> arr[] = {2, 2, 2, 3, 2, 2}, sum = 10<br><strong>Output:<\/strong> True<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"406\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Problem Statement Example\"  class=\"wp-image-2505 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Problem-Statement-Example.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Problem-Statement-Example.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Problem-Statement-Example-300x119.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Problem-Statement-Example-768x305.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Problem-Statement-Example-380x151.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Problem-Statement-Example-550x218.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Problem-Statement-Example-800x317.jpg 800w\" ><\/figure><\/div>\n\n\n\n<h2 id=\"recursive-approach\">Recursive Approach<\/h2>\n\n\n\n<p>For this approach, we have two cases.&nbsp;<\/p>\n\n\n\n<ul><li>Let&#8217;s take the last element and now the sum = target sum \u2013 value of \u2018last\u2019 element and elements remaining = size of array \u2013 1.<\/li><li>Now&nbsp; don&#8217;t take the \u2018last\u2019 element and now the&nbsp; sum = target sum and elements remaining = size of array \u2013 1.<\/li><\/ul>\n\n\n\n<p><strong>Dry Run of the Approach:<\/strong><\/p>\n\n\n\n<p>Suppose n is the size of the array.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>isThereSubsetSum(arr, n, sum) = isThereSubsetSum(arr, n-1, sum) ||&nbsp; isThereSubsetSum(arr, n-1, sum-arr[n-1])<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><strong>Base Cases<\/strong><\/p>\n\n\n\n<p>isThereSubsetSum(arr, n, sum) = false, if sum &gt; 0 and n == 0<br>isThereSubsetSum(arr, n, sum) = true, if sum == 0<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"687\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dry Run of Recursive Approach\"  class=\"wp-image-2504 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run--1024x687.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run--1024x687.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run--300x201.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run--768x515.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run--380x255.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run--550x369.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run--800x536.jpg 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run--1160x778.jpg 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Dry-Run-.jpg 1214w\" ><\/figure><\/div>\n\n\n\n<p><\/p>\n\n\n\n<h3 id=\"c-implementation-of-recursive-approach\">C Implementation Of Recursive Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"c\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool isThereSubsetSum(int arr[], int n, int sum) {\n  if (sum == 0)\n    return true;\n  if (n == 0)\n    return false;\n\n  if (arr[n - 1] > sum)\n    return isThereSubsetSum(arr, n - 1, sum);\n\n  return isThereSubsetSum(arr, n - 1, sum) ||\n    isThereSubsetSum(arr, n - 1, sum - arr[n - 1]);\n}<\/pre>\n\n\n\n<h3 id=\"-java-implementation-of-recursive-approach\"><span id=\"java-implementation-of-recursive-approach\"><meta charset=\"utf-8\">Java Implementation Of Recursive Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static boolean isThereSubsetSum(int arr[],\n  int n, int sum) {\n\n  if (sum == 0)\n    return true;\n  if (n == 0)\n    return false;\n\n  if (arr[n - 1] > sum)\n    return isThereSubsetSum(arr, n - 1, sum);\n\n  return isThereSubsetSum(arr, n - 1, sum) ||\n    isThereSubsetSum(arr, n - 1, sum - arr[n - 1]);\n}<\/pre>\n\n\n\n<h3 id=\"-python-implementation-of-recursive-approach\"><span id=\"python-implementation-of-recursive-approach\"><meta charset=\"utf-8\">Python Implementation Of Recursive Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def isThereSubsetSum(arr, n, sum):\n    if (sum == 0):\n        return True\n    if (n == 0):\n        return False\n \n    if (arr[n - 1] > sum):\n        return isThereSubsetSum(arr, n - 1, sum)\n \n    return isThereSubsetSum(\n        arr, n-1, sum) or isThereSubsetSum(\n        arr, n-1, sum-arr[n-1])<\/pre>\n\n\n\n<p><strong>Time complexity:<\/strong> The above approach may try all the possible subsets of a given array in the worst case. Therefore the time complexity of the above approach is exponential.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"dynamic-programming-approach\">Dynamic Programming Approach<\/h2>\n\n\n\n<p>In this approach, we will make a 2D array of size equal to (size of array + 1) * (target sum + 1) of boolean type. The state dp[i][j] will be true if there is a subset of elements from A[0\u2026.i] with a sum value equal to <strong>j<\/strong>.<\/p>\n\n\n\n<p><strong>Approach:<\/strong><\/p>\n\n\n\n<ul><li>We make a boolean dp[][] and fill it in a top-down manner.<\/li><li>The value of dp[i][j] will be true if there exists a subset of dp[0..i] with a sum equal to <strong>j<\/strong>., otherwise false<\/li><li>Finally, we return <strong>dp[n][sum]<\/strong><\/li><\/ul>\n\n\n\n<h3 id=\"c-implementation-for-subset-sum\">C Implementation For Subset Sum<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"c\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool isThereSubsetSum(int arr[], int n, int sum) {\n\n  bool dp[n + 1][sum + 1];\n  for (int i = 0; i &lt;= n; i++)\n    dp[i][0] = true;\n\n  for (int i = 1; i &lt;= sum; i++)\n    dp[0][i] = false;\n  for (int i = 1; i &lt;= n; i++) {\n    for (int j = 1; j &lt;= sum; j++) {\n      if (j &lt; arr[i - 1])\n        dp[i][j] = dp[i - 1][j];\n      if (j >= arr[i - 1])\n        dp[i][j] = dp[i - 1][j] ||\n        dp[i - 1][j - arr[i - 1]];\n    }\n  }\n  return dp[n][sum];\n}<\/pre>\n\n\n\n<h3 id=\"-java-implementation-for-subset-sum\"><span id=\"java-implementation-for-subset-sum\"><meta charset=\"utf-8\">Java Implementation For Subset Sum<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">static boolean isThereSubsetSum(int arr[], int n, int sum) {\n  boolean dp[][] = new boolean[n + 1][sum + 1];\n  for (int i = 0; i &lt;= n; i++)\n    dp[i][0] = true;\n\n  for (int i = 1; i &lt;= sum; i++)\n    dp[0][i] = false;\n\n  for (int i = 1; i &lt;= sum; i++) {\n    for (int j = 1; j &lt;= n; j++) {\n      if (j &lt; arr[i - 1])\n        dp[i][j] = dp[i - 1][j];\n      if (j >= arr[i - 1])\n        dp[i][j] = dp[i - 1][j] ||\n        dp[i - 1][j - arr[i - 1]];\n    }\n  }\n  return dp[n][sum];\n}<\/pre>\n\n\n\n<h3 id=\"-python-implementation-for-subset-sum\"><span id=\"python-implementation-for-subset-sum\"><meta charset=\"utf-8\">Python Implementation For Subset Sum<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def isThereSubsetSum(arr, n, sum):\n     \n    dp =([[False for i in range(sum + 1)]\n            for i in range(n + 1)])\n     \n    for i in range(n + 1):\n        dp[i][0] = True\n         \n    for i in range(1, sum + 1):\n         dp[0][i]= False\n             \n   \n    for i in range(1, n + 1):\n        for j in range(1, sum + 1):\n            if j&lt;arr[i-1]:\n                dp[i][j] = dp[i-1][j]\n            if j>= arr[i-1]:\n                dp[i][j] = (dp[i-1][j] or\n                                dp[i - 1][j-arr[i-1]])\n     \n    return dp[n][sum]<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N * sum) where N is the size of the array.<br><strong>Space Complexity:<\/strong> O(N * sum) where N is the size of the array.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/minimum-difference-subsets\/\" target=\"_blank\">Minimum Difference Subsets<\/a><br><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/subset-sum-problem\/\" target=\"_blank\">Subset Sum Problem<\/a><br><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/equal-average-partition\/\" target=\"_blank\">Equal Average Partition<\/a><br><a href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\" rel=\"noreferrer noopener\">Dynamic Programming<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>What subset sum problem gives a suitable example?<\/strong><br>The Subset-Sum Problem is to find a subset&#8217; of the given array A = (A1 A2 A3\u2026An) where the elements of the array A are n positive integers in such a way that a&#8217;\u2208A and summation of the elements of that subsets is equal to some positive integer S.<\/p>\n\n\n\n<p><strong>Is the subset sum problem NP-hard?<\/strong><br>Yes, it is an NP-hard problem.<\/p>\n\n\n\n<p><strong>Is subset-sum an optimization problem?<\/strong><br>Yes, subset-sum is an optimization problem because it has a variety of algorithms for tackling it.<\/p>\n\n\n\n<p><strong>How do you solve subsets?<\/strong><br>Subsets can be solved using backtracking and dynamic programming with efficient time complexity.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an array of non-negative integers and an integer sum. We have to tell whether there&hellip;\n","protected":false},"author":5,"featured_media":2503,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[399,416],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2501"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2501"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2501\/revisions"}],"predecessor-version":[{"id":21919,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2501\/revisions\/21919"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2503"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2501"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2501"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2501"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}