3 Partition Problem

3-partition problem: Given a set S of positive integers, determine if it can be partitioned into three disjoint subsets that all have same sum and they cover S.


 

The 3-partition problem is a special case of Partition Problem, which in turn is related to the Subset Sum Problem (which itself is a special case of the Knapsack Problem). In the partition problem, the goal is to partition S into two subsets with equal sum. In 3-partition problem, the goal is to partition S into 3 subsets with equal sum.

For example,

S = { 7, 3, 2, 1, 5, 4, 8 }

We can partition S into three partitions each having sum 10.

S1 = {7, 3}
S2 = {5, 4, 1}
S3 = {8, 2}

Note that there can be multiple solutions to a single set.

 


 

We can start by calculating the sum of all elements St in the set. If St is not divisible by 3, we can’t divide the array into three subsets with equal sum. If St is divisible by 3, we check if 3 subsets with sum of elements equal to St/3 exists or not. We can find this by considering each item in the given array one by one and for each item there are three possibilities –
 

  1. We include the current item in the first subset and recurse for remaining items with remaining sum.
     
  2. We include the current item in the second subset and recurse for remaining items with remaining sum.
     
  3. We include the current item in the third subset and recurse for remaining items with remaining sum.
     

The base case of the recursion would be when no items are left. We return true when 3 subsets each with zero sum are found. We can optimize our code by calling case 2 only if case 1 doesn’t result in solution, and case 3 only if case 1 and 2 doesn’t result in any solution.

C++

Download   Run Code

Output:

Yes

The time complexity of above solution is exponential and auxiliary space used by the program is O(1) plus recursion overhead.

 


 

The problem has an optimal substructure and it also exhibits overlapping subproblems i.e. the problem can be split into smaller subproblems and same subproblems will get computed again and again. We can easily prove this by drawing a recursion tree of above code for a very large input.

We can use Dynamic Programming to solve this problem by saving subproblem solutions in memory rather than computing them again and again. The following top-down approach uses std::unordered_map to achieve that.

C++

Download   Run Code

Output:

Yes

 
Exercise: Extend the solution to k-partitions and Print all partitions.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz