{"id":26400,"date":"2017-10-26T22:04:25","date_gmt":"2017-10-26T16:34:25","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26400"},"modified":"2017-10-26T22:04:25","modified_gmt":"2017-10-26T16:34:25","slug":"c-programming-partition-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-partition-problem\/","title":{"rendered":"C Programming &#8211; Partition Problem"},"content":{"rendered":"<p>Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.<span id=\"more-21579\"><\/span><\/p>\n<p>Examples<\/p>\n<pre>arr[] = {1, 5, 11, 5}\r\nOutput: true \r\nThe array can be partitioned as {1, 5, 5} and {11}\r\n\r\narr[] = {1, 5, 3}\r\nOutput: false \r\nThe array cannot be partitioned into equal sum sets.<\/pre>\n<p>Following are the two main steps to solve this problem:<\/p>\n<ul>\n<li>Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum, so return false.<\/li>\n<li>If sum of array elements is even, calculate sum\/2 and find a subset of array with sum equal to sum\/2.<\/li>\n<\/ul>\n<p>The first step is simple. The second step is crucial, it can be solved either using recursion or Dynamic Programming.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Recursive Solution<\/strong><br \/>\nFollowing is the recursive property of the second step mentioned above.<\/p>\n<pre>et isSubsetSum(arr, n, sum\/2) be the function that returns true if \r\nthere is a subset of arr[0..n-1] with sum equal to sum\/2\r\n\r\nThe isSubsetSum problem can be divided into two subproblems\r\n a) isSubsetSum() without considering last element \r\n    (reducing n to n-1)\r\n b) isSubsetSum considering the last element \r\n    (reducing sum\/2 by arr[n-1] and n to n-1)\r\nIf any of the above the above subproblems return true, then return true. \r\nisSubsetSum (arr, n, sum\/2) = isSubsetSum (arr, n-1, sum\/2) ||\r\n                              isSubsetSum (arr, n-1, sum\/2 - arr[n-1])<\/pre>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20%20recursive%20C%20program%20for%20partition%20problem%0A%23include%20%3Cstdio.h%3E%0A%20%0A%2F%2F%20A%20utility%20function%20that%20returns%20true%20if%20there%20is%20%0A%2F%2F%20a%20subset%20of%20arr%5B%5D%20with%20sun%20equal%20to%20given%20sum%0Abool%20isSubsetSum%20(int%20arr%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%20%0A%20%20%20%2F%2F%20ignore%20it%0A%20%20%20if%20(arr%5Bn-1%5D%20%3E%20sum)%0A%20%20%20%20%20return%20isSubsetSum%20(arr%2C%20n-1%2C%20sum)%3B%0A%20%0A%20%20%20%2F*%20else%2C%20check%20if%20sum%20can%20be%20obtained%20by%20any%20of%20%0A%20%20%20%20%20%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%0A%20%20%20*%2F%0A%20%20%20return%20isSubsetSum%20(arr%2C%20n-1%2C%20sum)%20%7C%7C%20%0A%20%20%20%20%20%20%20%20%20%20isSubsetSum%20(arr%2C%20n-1%2C%20sum-arr%5Bn-1%5D)%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20true%20if%20arr%5B%5D%20can%20be%20partitioned%20in%20two%0A%2F%2F%20%20subsets%20of%20equal%20sum%2C%20otherwise%20false%0Abool%20findPartiion%20(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Calculate%20sum%20of%20the%20elements%20in%20array%0A%20%20%20%20int%20sum%20%3D%200%3B%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20sum%20%2B%3D%20arr%5Bi%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20sum%20is%20odd%2C%20there%20cannot%20be%20two%20subsets%20%0A%20%20%20%20%2F%2F%20with%20equal%20sum%0A%20%20%20%20if%20(sum%252%20!%3D%200)%0A%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%2F%2F%20Find%20if%20there%20is%20subset%20with%20sum%20equal%20to%0A%20%20%20%20%2F%2F%20half%20of%20total%20sum%0A%20%20%20%20return%20isSubsetSum%20(arr%2C%20n%2C%20sum%2F2)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20int%20arr%5B%5D%20%3D%20%7B3%2C%201%2C%205%2C%209%2C%2012%7D%3B%0A%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20if%20(findPartiion(arr%2C%20n)%20%3D%3D%20true)%0A%20%20%20%20%20printf(%22Can%20be%20divided%20into%20two%20subsets%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22of%20equal%20sum%22)%3B%0A%20%20else%0A%20%20%20%20%20printf(%22Can%20not%20be%20divided%20into%20two%20subsets%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%20of%20equal%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>Can be divided into two subsets of equal sum<\/pre>\n<p>Time Complexity: O(2^n) In worst case, this solution tries two possibilities (whether to include or exclude) for every element.<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>Dynamic Programming Solution<\/strong><br \/>\nThe problem can be solved using dynamic programming when the sum of the elements is not too big. We can create a 2D array part[][] of size (sum\/2)*(n+1). And we can construct the solution in bottom up manner such that every filled entry has following property<\/p>\n<pre>part[i][j] = true if a subset of {arr[0], arr[1], ..arr[j-1]} has sum \r\n             equal to i, otherwise false<\/pre>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20A%20Dynamic%20Programming%20based%20C%20program%20to%20partition%20problem%0A%23include%20%3Cstdio.h%3E%0A%20%0A%2F%2F%20Returns%20true%20if%20arr%5B%5D%20can%20be%20partitioned%20in%20two%20subsets%20of%0A%2F%2F%20equal%20sum%2C%20otherwise%20false%0Abool%20findPartiion%20(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20sum%20%3D%200%3B%0A%20%20%20%20int%20i%2C%20j%3B%0A%20%20%20%0A%20%20%20%20%2F%2F%20Caculcate%20sun%20of%20all%20elements%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20sum%20%2B%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%0A%20%20%20%20if%20(sum%252%20!%3D%200)%20%20%0A%20%20%20%20%20%20%20return%20false%3B%0A%20%20%20%0A%20%20%20%20bool%20part%5Bsum%2F2%2B1%5D%5Bn%2B1%5D%3B%0A%20%20%20%20%20%0A%20%20%20%20%2F%2F%20initialize%20top%20row%20as%20true%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%3D%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20part%5B0%5D%5Bi%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%0A%20%20%20%20%2F%2F%20initialize%20leftmost%20column%2C%20except%20part%5B0%5D%5B0%5D%2C%20as%200%0A%20%20%20%20for%20(i%20%3D%201%3B%20i%20%3C%3D%20sum%2F2%3B%20i%2B%2B)%0A%20%20%20%20%20%20part%5Bi%5D%5B0%5D%20%3D%20false%3B%20%20%20%20%20%0A%20%20%20%20%20%20%0A%20%20%20%20%20%2F%2F%20Fill%20the%20partition%20table%20in%20botton%20up%20manner%20%0A%20%20%20%20%20for%20(i%20%3D%201%3B%20i%20%3C%3D%20sum%2F2%3B%20i%2B%2B)%20%20%0A%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20for%20(j%20%3D%201%3B%20j%20%3C%3D%20n%3B%20j%2B%2B)%20%20%0A%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20part%5Bi%5D%5Bj%5D%20%3D%20part%5Bi%5D%5Bj-1%5D%3B%0A%20%20%20%20%20%20%20%20%20if%20(i%20%3E%3D%20arr%5Bj-1%5D)%0A%20%20%20%20%20%20%20%20%20%20%20part%5Bi%5D%5Bj%5D%20%3D%20part%5Bi%5D%5Bj%5D%20%7C%7C%20part%5Bi%20-%20arr%5Bj-1%5D%5D%5Bj-1%5D%3B%0A%20%20%20%20%20%20%20%7D%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%7D%20%20%20%20%0A%20%20%20%20%20%20%0A%20%20%20%20%2F*%20%2F%2F%20uncomment%20this%20part%20to%20print%20table%20%0A%20%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%3D%20sum%2F2%3B%20i%2B%2B)%20%20%0A%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20for%20(j%20%3D%200%3B%20j%20%3C%3D%20n%3B%20j%2B%2B)%20%20%0A%20%20%20%20%20%20%20%20%20%20printf%20(%22%254d%22%2C%20part%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%20%20%20%20%20%0A%20%20%20%20%20return%20part%5Bsum%2F2%5D%5Bn%5D%3B%0A%7D%20%20%20%20%20%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20funtion%0Aint%20main()%0A%7B%0A%20%20int%20arr%5B%5D%20%3D%20%7B3%2C%201%2C%201%2C%202%2C%202%2C%201%7D%3B%0A%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20if%20(findPartiion(arr%2C%20n)%20%3D%3D%20true)%0A%20%20%20%20%20printf(%22Can%20be%20divided%20into%20two%20subsets%20of%20equal%20sum%22)%3B%0A%20%20else%0A%20%20%20%20%20printf(%22Can%20not%20be%20divided%20into%20two%20subsets%20of%20equal%20sum%22)%3B%0A%20%20getchar()%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>Can be divided into two subsets of equal sum<\/pre>\n<p>Following diagram shows the values in partition table.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-26413\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Partition-Problem.png\" alt=\"Partition Problem\" width=\"847\" height=\"540\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Partition-Problem.png 847w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Partition-Problem-300x191.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Partition-Problem-768x490.png 768w\" sizes=\"(max-width: 847px) 100vw, 847px\" \/><\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C Programming &#8211; Partition Problem &#8211; Dynamic Programming Partition problem is to determine whether a given set can be partitioned into two subsets<\/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":[78704,78733,78718,78715,78705,78710,78731,72847,72842,72845,70483,72848,72840,72846,72994,72843,72992,72854,72844,72850,72839,78713,78703,78724,78721,78723,78725,78702,78727,78707,78735,78728,78730,78714,78706,78719,78712,78734,72852,78716,72855,78717,72853,72851],"class_list":["post-26400","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming","category-coding","category-dynamic-programming","tag-3-partition-problem","tag-3-partition-problem-in-c","tag-balanced-partition","tag-balanced-partition-of-array","tag-balanced-partition-problem","tag-balanced-partition-problem-dynamic-programming","tag-c-program-for-partition-problem","tag-concept-of-dynamic-programming","tag-define-dynamic-programming","tag-definition-of-dynamic-programming","tag-dynamic-programming","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-in-python","tag-dynamic-programming-problems","tag-dynamic-programming-python","tag-dynamic-programming-set-1","tag-dynamic-programming-software","tag-explain-dynamic-programming","tag-how-to-solve-dynamic-programming-problems","tag-how-to-solve-partition-problem","tag-k-partition-problem","tag-k-partition-problem-dynamic-programming","tag-linear-partition-problem","tag-partition-array-in-equal-halves-with-minimum-sum-difference","tag-partition-array-into-equal-sums","tag-partition-problem","tag-partition-problem-c","tag-partition-problem-dynamic-programming","tag-partition-problem-in-c","tag-partition-problem-in-c-code","tag-partition-problem-in-c-program","tag-partition-problem-in-dynamic-programming","tag-partition-problem-java","tag-partition-problem-minimum-difference","tag-partition-problem-np-complete","tag-partition-problem-python","tag-problems-on-dynamic-programming","tag-set-partition-problem","tag-simple-dynamic-programming-example","tag-the-partition-problem","tag-types-of-dynamic-programming","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26400","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=26400"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26400\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26400"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26400"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26400"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}