{"id":26419,"date":"2017-10-26T22:02:03","date_gmt":"2017-10-26T16:32:03","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26419"},"modified":"2017-10-26T22:02:03","modified_gmt":"2017-10-26T16:32:03","slug":"java-programming-partition-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-partition-problem\/","title":{"rendered":"Java 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=\u201djava\u201d manual=\u201d%2F%2F%20A%20recursive%20Java%20solution%20for%20partition%20problem%0Aimport%20java.io.*%3B%0A%20%0Aclass%20Partition%0A%7B%0A%20%20%20%20%2F%2F%20A%20utility%20function%20that%20returns%20true%20if%20there%20is%20a%0A%20%20%20%20%2F%2F%20subset%20of%20arr%5B%5D%20with%20sun%20equal%20to%20given%20sum%0A%20%20%20%20static%20boolean%20isSubsetSum%20(int%20arr%5B%5D%2C%20int%20n%2C%20int%20sum)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Base%20Cases%0A%20%20%20%20%20%20%20%20if%20(sum%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20if%20(n%20%3D%3D%200%20%26%26%20sum%20!%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20last%20element%20is%20greater%20than%20sum%2C%20then%20ignore%20it%0A%20%20%20%20%20%20%20%20if%20(arr%5Bn-1%5D%20%3E%20sum)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20isSubsetSum%20(arr%2C%20n-1%2C%20sum)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20else%2C%20check%20if%20sum%20can%20be%20obtained%20by%20any%20of%0A%20%20%20%20%20%20%20%20%20%20%20the%20following%0A%20%20%20%20%20%20%20%20(a)%20including%20the%20last%20element%0A%20%20%20%20%20%20%20%20(b)%20excluding%20the%20last%20element%0A%20%20%20%20%20%20%20%20*%2F%0A%20%20%20%20%20%20%20%20return%20isSubsetSum%20(arr%2C%20n-1%2C%20sum)%20%7C%7C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20isSubsetSum%20(arr%2C%20n-1%2C%20sum-arr%5Bn-1%5D)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Returns%20true%20if%20arr%5B%5D%20can%20be%20partitioned%20in%20two%0A%20%20%20%20%2F%2F%20subsets%20of%20equal%20sum%2C%20otherwise%20false%0A%20%20%20%20static%20boolean%20findPartition%20(int%20arr%5B%5D%2C%20int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Calculate%20sum%20of%20the%20elements%20in%20array%0A%20%20%20%20%20%20%20%20int%20sum%20%3D%200%3B%0A%20%20%20%20%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%20%20%20%20%20%20sum%20%2B%3D%20arr%5Bi%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20sum%20is%20odd%2C%20there%20cannot%20be%20two%20subsets%0A%20%20%20%20%20%20%20%20%2F%2F%20with%20equal%20sum%0A%20%20%20%20%20%20%20%20if%20(sum%252%20!%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20if%20there%20is%20subset%20with%20sum%20equal%20to%20half%0A%20%20%20%20%20%20%20%20%2F%2F%20of%20total%20sum%0A%20%20%20%20%20%20%20%20return%20isSubsetSum%20(arr%2C%20n%2C%20sum%2F2)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*Driver%20function%20to%20check%20for%20above%20function*%2F%0A%20%20%20%20public%20static%20void%20main%20(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B3%2C%201%2C%205%2C%209%2C%2012%7D%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20if%20(findPartition(arr%2C%20n)%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Can%20be%20divided%20into%20two%20%22%2B%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%22subsets%20of%20equal%20sum%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Can%20not%20be%20divided%20into%20%22%20%2B%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%22two%20subsets%20of%20equal%20sum%22)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJava\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=\u201djava\u201d manual=\u201d%2F%2F%20A%20dynamic%20programming%20based%20Java%20program%20for%20partition%20problem%0Aimport%20java.io.*%3B%0A%20%0Aclass%20Partition%20%7B%0A%20%0A%20%20%20%20%2F%2F%20Returns%20true%20if%20arr%5B%5D%20can%20be%20partitioned%20in%20two%20subsets%20of%0A%20%20%20%20%2F%2F%20equal%20sum%2C%20otherwise%20false%0A%20%20%20%20static%20boolean%20findPartition%20(int%20arr%5B%5D%2C%20int%20n)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20sum%20%3D%200%3B%0A%20%20%20%20%20%20%20%20int%20i%2C%20j%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Caculcate%20sun%20of%20all%20elements%0A%20%20%20%20%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20sum%20%2B%3D%20arr%5Bi%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(sum%252%20!%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20boolean%20part%5B%5D%5B%5D%3Dnew%20boolean%5Bsum%2F2%2B1%5D%5Bn%2B1%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20initialize%20top%20row%20as%20true%0A%20%20%20%20%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%20%20%20%20%20%20%20part%5B0%5D%5Bi%5D%20%3D%20true%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20initialize%20leftmost%20column%2C%20except%20part%5B0%5D%5B0%5D%2C%20as%200%0A%20%20%20%20%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%20%20%20%20%20%20%20part%5Bi%5D%5B0%5D%20%3D%20false%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Fill%20the%20partition%20table%20in%20botton%20up%20manner%0A%20%20%20%20%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%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(j%20%3D%201%3B%20j%20%3C%3D%20n%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%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%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%20%20%20%20%20%20%20%20%20%20part%5Bi%5D%5Bj%5D%20%3D%20part%5Bi%5D%5Bj%5D%20%7C%7C%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%20part%5Bi%20-%20arr%5Bj-1%5D%5D%5Bj-1%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20%2F%2F%20uncomment%20this%20part%20to%20print%20table%0A%20%20%20%20%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%3D%20sum%2F2%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(j%20%3D%200%3B%20j%20%3C%3D%20n%3B%20j%2B%2B)%0A%20%20%20%20%20%20%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%20%20%20%20%20%20printf(%22%5Cn%22)%3B%0A%20%20%20%20%20%20%20%20%7D%20*%2F%0A%20%0A%20%20%20%20%20%20%20%20return%20part%5Bsum%2F2%5D%5Bn%5D%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*Driver%20function%20to%20check%20for%20above%20function*%2F%0A%20%20%20%20public%20static%20void%20main%20(String%5B%5D%20args)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B3%2C%201%2C%201%2C%202%2C%202%2C1%7D%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20if%20(findPartition(arr%2C%20n)%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Can%20be%20divided%20into%20two%20%22%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%22subsets%20of%20equal%20sum%22)%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.println(%22Can%20not%20be%20divided%20into%22%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%22%20two%20subsets%20of%20equal%20sum%22)%3B%0A%20%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJava\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>Java 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,1,70145,2139],"tags":[78704,78726,78718,78715,78705,78710,72847,72842,72845,70483,72848,72840,72846,72987,72985,72843,72854,72844,72850,72839,78713,78720,78703,78724,78721,78723,78725,78702,78707,78714,78708,78711,78722,78706,78709,78719,78712,72852,78716,72855,78717,72853,72851],"class_list":["post-26419","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-dynamic-programming","category-java","tag-3-partition-problem","tag-3-partition-problem-in-java","tag-balanced-partition","tag-balanced-partition-of-array","tag-balanced-partition-problem","tag-balanced-partition-problem-dynamic-programming","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-java","tag-dynamic-programming-java","tag-dynamic-programming-problems","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-java-program-for-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-dynamic-programming","tag-partition-problem-in-dynamic-programming","tag-partition-problem-in-java-code","tag-partition-problem-in-java-program","tag-partition-problem-in-java-progs","tag-partition-problem-java","tag-partition-problem-java-coding","tag-partition-problem-minimum-difference","tag-partition-problem-np-complete","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\/26419","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=26419"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26419\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26419"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26419"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26419"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}