{"id":27159,"date":"2018-01-03T21:57:58","date_gmt":"2018-01-03T16:27:58","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27159"},"modified":"2018-01-03T21:57:58","modified_gmt":"2018-01-03T16:27:58","slug":"c-programming-subset-sum-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-subset-sum-problem\/","title":{"rendered":"C Programming &#8211; Subset Sum Problem"},"content":{"rendered":"<p>Given a set of non-negative integers, and a value <em>sum<\/em>, determine if there is a subset of the given set with sum equal to given <em>sum<\/em>.<span id=\"more-28860\"><\/span><\/p>\n<pre>Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9\r\nOutput:  True  \/\/There is a subset (4, 5) with sum 9.<\/pre>\n<p>Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to <em>sum<\/em>. n is the number of elements in set[].<\/p>\n<p>The isSubsetSum problem can be divided into two subproblems<br \/>\n\u2026a) Include the last element, recur for n = n-1, sum = sum \u2013 set[n-1]\n\u2026b) Exclude the last element, recur for n = n-1.<br \/>\nIf any of the above the above subproblems return true, then return true.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>Following is the recursive formula for isSubsetSum() problem.<\/p>\n<pre>isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) || \r\n                           isSubsetSum(set, n-1, sum-set[n-1])\r\n<strong>Base Cases:<\/strong>\r\nisSubsetSum(set, n, sum) = false, if sum > 0 and n == 0\r\nisSubsetSum(set, n, sum) = true, if sum == 0 \r\n<\/pre>\n<p>Following is naive recursive implementation that simply follows the recursive structure mentioned above.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20recursive%20solution%20for%20subset%20sum%20problem%0A%23include%20%3Cstdio.h%3E%0A%20%0A%2F%2F%20Returns%20true%20if%20there%20is%20a%20subset%20of%20set%5B%5D%20with%20sun%20equal%20to%20given%20sum%0Abool%20isSubsetSum(int%20set%5B%5D%2C%20int%20n%2C%20int%20sum)%0A%7B%0A%20%20%20%2F%2F%20Base%20Cases%0A%20%20%20if%20(sum%20%3D%3D%200)%0A%20%20%20%20%20return%20true%3B%0A%20%20%20if%20(n%20%3D%3D%200%20%26%26%20sum%20!%3D%200)%0A%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%2F%2F%20If%20last%20element%20is%20greater%20than%20sum%2C%20then%20ignore%20it%0A%20%20%20if%20(set%5Bn-1%5D%20%3E%20sum)%0A%20%20%20%20%20return%20isSubsetSum(set%2C%20n-1%2C%20sum)%3B%0A%20%0A%20%20%20%2F*%20else%2C%20check%20if%20sum%20can%20be%20obtained%20by%20any%20of%20the%20following%0A%20%20%20%20%20%20(a)%20including%20the%20last%20element%0A%20%20%20%20%20%20(b)%20excluding%20the%20last%20element%20%20%20*%2F%0A%20%20%20return%20isSubsetSum(set%2C%20n-1%2C%20sum)%20%7C%7C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20isSubsetSum(set%2C%20n-1%2C%20sum-set%5Bn-1%5D)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20int%20set%5B%5D%20%3D%20%7B3%2C%2034%2C%204%2C%2012%2C%205%2C%202%7D%3B%0A%20%20int%20sum%20%3D%209%3B%0A%20%20int%20n%20%3D%20sizeof(set)%2Fsizeof(set%5B0%5D)%3B%0A%20%20if%20(isSubsetSum(set%2C%20n%2C%20sum)%20%3D%3D%20true)%0A%20%20%20%20%20printf(%22Found%20a%20subset%20with%20given%20sum%22)%3B%0A%20%20else%0A%20%20%20%20%20printf(%22No%20subset%20with%20given%20sum%22)%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output :<\/strong><\/p>\n<pre> Found a subset with given sum<\/pre>\n<p>The above solution may try all subsets of given set in worst case. Therefore time complexity of the above solution is exponential. The problem is in-fact NP-Complete (There is no known polynomial time solution for this problem).<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>We can solve the problem in Pseudo-polynomial time using Dynamic programming. <\/strong>We create a boolean 2D table subset[][] and fill it in bottom up manner. The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i., otherwise false. Finally, we return subset[sum][n]\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20Dynamic%20Programming%20solution%20for%20subset%20sum%20problem%0A%23include%20%3Cstdio.h%3E%0A%20%0A%2F%2F%20Returns%20true%20if%20there%20is%20a%20subset%20of%20set%5B%5D%20with%20sun%20equal%20to%20given%20sum%0Abool%20isSubsetSum(int%20set%5B%5D%2C%20int%20n%2C%20int%20sum)%0A%7B%0A%20%20%20%20%2F%2F%20The%20value%20of%20subset%5Bi%5D%5Bj%5D%20will%20be%20true%20if%20there%20is%20a%20%0A%20%20%20%20%2F%2F%20subset%20of%20set%5B0..j-1%5D%20with%20sum%20equal%20to%20i%0A%20%20%20%20bool%20subset%5Bsum%2B1%5D%5Bn%2B1%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20sum%20is%200%2C%20then%20answer%20is%20true%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20subset%5B0%5D%5Bi%5D%20%3D%20true%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20sum%20is%20not%200%20and%20set%20is%20empty%2C%20then%20answer%20is%20false%0A%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%3D%20sum%3B%20i%2B%2B)%0A%20%20%20%20%20%20subset%5Bi%5D%5B0%5D%20%3D%20false%3B%0A%20%0A%20%20%20%20%20%2F%2F%20Fill%20the%20subset%20table%20in%20botton%20up%20manner%0A%20%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%3D%20sum%3B%20i%2B%2B)%0A%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20for%20(int%20j%20%3D%201%3B%20j%20%3C%3D%20n%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20subset%5Bi%5D%5Bj%5D%20%3D%20subset%5Bi%5D%5Bj-1%5D%3B%0A%20%20%20%20%20%20%20%20%20if%20(i%20%3E%3D%20set%5Bj-1%5D)%0A%20%20%20%20%20%20%20%20%20%20%20subset%5Bi%5D%5Bj%5D%20%3D%20subset%5Bi%5D%5Bj%5D%20%7C%7C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20subset%5Bi%20-%20set%5Bj-1%5D%5D%5Bj-1%5D%3B%0A%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20%2F%2F%20uncomment%20this%20code%20to%20print%20table%0A%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%3D%20sum%3B%20i%2B%2B)%0A%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%3D%20n%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20printf%20(%22%254d%22%2C%20subset%5Bi%5D%5Bj%5D)%3B%0A%20%20%20%20%20%20%20printf(%22%5Cn%22)%3B%0A%20%20%20%20%20%7D%20*%2F%0A%20%0A%20%20%20%20%20return%20subset%5Bsum%5D%5Bn%5D%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20int%20set%5B%5D%20%3D%20%7B3%2C%2034%2C%204%2C%2012%2C%205%2C%202%7D%3B%0A%20%20int%20sum%20%3D%209%3B%0A%20%20int%20n%20%3D%20sizeof(set)%2Fsizeof(set%5B0%5D)%3B%0A%20%20if%20(isSubsetSum(set%2C%20n%2C%20sum)%20%3D%3D%20true)%0A%20%20%20%20%20printf(%22Found%20a%20subset%20with%20given%20sum%22)%3B%0A%20%20else%0A%20%20%20%20%20printf(%22No%20subset%20with%20given%20sum%22)%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>Found a subset with given sum<\/pre>\n<p>Time complexity of the above solution is O(sum*n).<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C Programming &#8211; Subset Sum Problem &#8211; Dynamic Programming Given a set of non-negative integers, and a value sum, determine if there is a subset <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,69866,1,70145],"tags":[72852,72855,80976,80977,70593,70616,80973,80974,74496],"class_list":["post-27159","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming","category-coding","category-dynamic-programming","tag-problems-on-dynamic-programming","tag-simple-dynamic-programming-example","tag-subset-sum-in-c-program","tag-subset-sum-in-java-program","tag-subset-sum-problem","tag-subset-sum-problem-dynamic-programming","tag-subset-sum-problem-in-c","tag-subset-sum-problem-in-java-find-all-subsets-that-sum-to-a-particular-value","tag-sum-of-subset-problem-using-backtracking"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27159","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27159"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27159\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27159"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27159"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27159"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}