{"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=&#8221;banner&#8221;]\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<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Java<\/span> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\">\/\/ A recursive Java solution for partition problem<br\/>import java.io.*;<br\/> <br\/>class Partition<br\/>{<br\/>    \/\/ A utility function that returns true if there is a<br\/>    \/\/ subset of arr[] with sun equal to given sum<br\/>    static boolean isSubsetSum (int arr[], int n, int sum)<br\/>    {<br\/>        \/\/ Base Cases<br\/>        if (sum == 0)<br\/>            return true;<br\/>        if (n == 0 &amp;&amp; sum != 0)<br\/>            return false;<br\/> <br\/>        \/\/ If last element is greater than sum, then ignore it<br\/>        if (arr[n-1] &gt; sum)<br\/>            return isSubsetSum (arr, n-1, sum);<br\/> <br\/>        \/* else, check if sum can be obtained by any of<br\/>           the following<br\/>        (a) including the last element<br\/>        (b) excluding the last element<br\/>        *\/<br\/>        return isSubsetSum (arr, n-1, sum) ||<br\/>               isSubsetSum (arr, n-1, sum-arr[n-1]);<br\/>    }<br\/> <br\/>    \/\/ Returns true if arr[] can be partitioned in two<br\/>    \/\/ subsets of equal sum, otherwise false<br\/>    static boolean findPartition (int arr[], int n)<br\/>    {<br\/>        \/\/ Calculate sum of the elements in array<br\/>        int sum = 0;<br\/>        for (int i = 0; i &lt; n; i++)<br\/>            sum += arr[i];<br\/> <br\/>        \/\/ If sum is odd, there cannot be two subsets<br\/>        \/\/ with equal sum<br\/>        if (sum%2 != 0)<br\/>            return false;<br\/> <br\/>        \/\/ Find if there is subset with sum equal to half<br\/>        \/\/ of total sum<br\/>        return isSubsetSum (arr, n, sum\/2);<br\/>    }<br\/> <br\/>    \/*Driver function to check for above function*\/<br\/>    public static void main (String[] args)<br\/>    {<br\/> <br\/>        int arr[] = {3, 1, 5, 9, 12};<br\/>        int n = arr.length;<br\/>        if (findPartition(arr, n) == true)<br\/>            System.out.println(&quot;Can be divided into two &quot;+<br\/>                                &quot;subsets of equal sum&quot;);<br\/>        else<br\/>            System.out.println(&quot;Can not be divided into &quot; +<br\/>                                &quot;two subsets of equal sum&quot;);<br\/>    }<br\/>}<\/code><\/pre> <\/div>\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=&#8221;banner&#8221;]\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<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">Java<\/span> <\/div> <pre class=\"language-java code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-java code-embed-code\">\/\/ A dynamic programming based Java program for partition problem<br\/>import java.io.*;<br\/> <br\/>class Partition {<br\/> <br\/>    \/\/ Returns true if arr[] can be partitioned in two subsets of<br\/>    \/\/ equal sum, otherwise false<br\/>    static boolean findPartition (int arr[], int n)<br\/>    {<br\/>        int sum = 0;<br\/>        int i, j;<br\/> <br\/>        \/\/ Caculcate sun of all elements<br\/>        for (i = 0; i &lt; n; i++)<br\/>            sum += arr[i];<br\/> <br\/>        if (sum%2 != 0)<br\/>            return false;<br\/> <br\/>        boolean part[][]=new boolean[sum\/2+1][n+1];<br\/> <br\/>        \/\/ initialize top row as true<br\/>        for (i = 0; i &lt;= n; i++)<br\/>            part[0][i] = true;<br\/> <br\/>        \/\/ initialize leftmost column, except part[0][0], as 0<br\/>        for (i = 1; i &lt;= sum\/2; i++)<br\/>            part[i][0] = false;<br\/> <br\/>        \/\/ Fill the partition table in botton up manner<br\/>        for (i = 1; i &lt;= sum\/2; i++)<br\/>        {<br\/>            for (j = 1; j &lt;= n; j++)<br\/>            {<br\/>                part[i][j] = part[i][j-1];<br\/>                if (i &gt;= arr[j-1])<br\/>                    part[i][j] = part[i][j] ||<br\/>                                 part[i - arr[j-1]][j-1];<br\/>            }<br\/>        }<br\/> <br\/>        \/* \/\/ uncomment this part to print table<br\/>        for (i = 0; i &lt;= sum\/2; i++)<br\/>        {<br\/>            for (j = 0; j &lt;= n; j++)<br\/>                printf (&quot;%4d&quot;, part[i][j]);<br\/>            printf(&quot;\\n&quot;);<br\/>        } *\/<br\/> <br\/>        return part[sum\/2][n];<br\/>    }<br\/> <br\/>    \/*Driver function to check for above function*\/<br\/>    public static void main (String[] args)<br\/>    {<br\/>        int arr[] = {3, 1, 1, 2, 2,1};<br\/>        int n = arr.length;<br\/>        if (findPartition(arr, n) == true)<br\/>            System.out.println(&quot;Can be divided into two &quot;<br\/>                               &quot;subsets of equal sum&quot;);<br\/>        else<br\/>            System.out.println(&quot;Can not be divided into&quot;<br\/>                            &quot; two subsets of equal sum&quot;);<br\/> <br\/>    }<br\/>}<\/code><\/pre> <\/div>\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=&#8221;banner&#8221;]\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}]}}