{"id":26418,"date":"2017-10-26T22:03:47","date_gmt":"2017-10-26T16:33:47","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26418"},"modified":"2017-10-26T22:03:47","modified_gmt":"2017-10-26T16:33:47","slug":"c-programming-partition-problem-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-partition-problem-2\/","title":{"rendered":"Cpp 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\">C++<\/span> <\/div> <pre class=\"language-cpp code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-cpp code-embed-code\">\/\/ A  recursive C program for partition problem<br\/>#include &lt;stdio.h&gt;<br\/> <br\/>\/\/ A utility function that returns true if there is <br\/>\/\/ a subset of arr[] with sun equal to given sum<br\/>bool 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 <br\/>   \/\/ 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\/>bool findPartiion (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<br\/>    \/\/ half of total sum<br\/>    return isSubsetSum (arr, n, sum\/2);<br\/>}<br\/> <br\/>\/\/ Driver program to test above function<br\/>int main()<br\/>{<br\/>  int arr[] = {3, 1, 5, 9, 12};<br\/>  int n = sizeof(arr)\/sizeof(arr[0]);<br\/>  if (findPartiion(arr, n) == true)<br\/>     printf(&quot;Can be divided into two subsets &quot;<br\/>            &quot;of equal sum&quot;);<br\/>  else<br\/>     printf(&quot;Can not be divided into two subsets&quot;<br\/>            &quot; of equal sum&quot;);<br\/>  return 0;<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\">C++<\/span> <\/div> <pre class=\"language-cpp code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-cpp code-embed-code\">\/\/ A Dynamic Programming based C program to partition problem<br\/>#include &lt;stdio.h&gt;<br\/> <br\/>\/\/ Returns true if arr[] can be partitioned in two subsets of<br\/>\/\/ equal sum, otherwise false<br\/>bool findPartiion (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\/>    bool part[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] || 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 program to test above funtion<br\/>int main()<br\/>{<br\/>  int arr[] = {3, 1, 1, 2, 2, 1};<br\/>  int n = sizeof(arr)\/sizeof(arr[0]);<br\/>  if (findPartiion(arr, n) == true)<br\/>     printf(&quot;Can be divided into two subsets of equal sum&quot;);<br\/>  else<br\/>     printf(&quot;Can not be divided into two subsets of equal sum&quot;);<br\/>  getchar();<br\/>  return 0;<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>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,83515,1,70145],"tags":[78704,78733,78718,78715,78705,78710,78731,72847,72842,72845,70483,72841,72848,72840,72849,72846,72843,72854,72844,72850,72839,78713,78703,78724,78721,78723,78725,78702,78727,78729,78707,78728,78730,78732,78714,78719,78712,72852,78716,72855,78717,72853,72851],"class_list":["post-26418","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","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-c","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-c","tag-dynamic-programming-in-data-structure","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-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-c-coding","tag-partition-problem-dynamic-programming","tag-partition-problem-in-c-code","tag-partition-problem-in-c-program","tag-partition-problem-in-c-progs","tag-partition-problem-in-dynamic-programming","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\/26418","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=26418"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26418\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26418"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26418"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26418"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}