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.

Examples

arr[] = {1, 5, 11, 5}
Output: true 
The array can be partitioned as {1, 5, 5} and {11}

arr[] = {1, 5, 3}
Output: false 
The array cannot be partitioned into equal sum sets.

Following are the two main steps to solve this problem:

  • Calculate sum of the array. If sum is odd, there can not be two subsets with equal sum, so return false.
  • If sum of array elements is even, calculate sum/2 and find a subset of array with sum equal to sum/2.

The first step is simple. The second step is crucial, it can be solved either using recursion or Dynamic Programming.

[ad type=”banner”]

Recursive Solution
Following is the recursive property of the second step mentioned above.

et isSubsetSum(arr, n, sum/2) be the function that returns true if 
there is a subset of arr[0..n-1] with sum equal to sum/2

The isSubsetSum problem can be divided into two subproblems
 a) isSubsetSum() without considering last element 
    (reducing n to n-1)
 b) isSubsetSum considering the last element 
    (reducing sum/2 by arr[n-1] and n to n-1)
If any of the above the above subproblems return true, then return true. 
isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) ||
                              isSubsetSum (arr, n-1, sum/2 - arr[n-1])
[pastacode lang=”cpp” manual=”%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” message=”C++” highlight=”” provider=”manual”/]

Output :

Can be divided into two subsets of equal sum

Time Complexity: O(2^n) In worst case, this solution tries two possibilities (whether to include or exclude) for every element.

[ad type=”banner”]

Dynamic Programming Solution
The 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

part[i][j] = true if a subset of {arr[0], arr[1], ..arr[j-1]} has sum 
             equal to i, otherwise false
[pastacode lang=”cpp” manual=”%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” message=”C++” highlight=”” provider=”manual”/]

Output :

Can be divided into two subsets of equal sum

Following diagram shows the values in partition table.

Partition Problem

[ad type=”banner”]