Challenge: Splitting the Pirate Loot

Solve the 3-Partition Problem.

We'll cover the following

Problem

3-Partition Problem

Partition a set of integers into three subsets with equal sums.

Input: A sequence of integers v1v_{1}, v2v_{2},…, vnv_{n}.

Output: Check whether it is possible to partition them into three subsets with equal sums, i.e., check whether there exist three disjoint sets S1S_{1}, S2S_{2}, S3S_{3} ⊆ {1,2,...,n1,2,...,n} such that S1S_{1} ∪∪ S2S_{2} ∪∪ S3S_{3} = {1,2,...,n1,2,...,n} and

∑i∈S1vi\sum_{i\in S_{1}} v_{i} = ∑j∈S2vj\sum_{j\in S_{2}} v_{j} = ∑k∈S3vk\sum_{k\in S_{3}} v_{k}

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.