# Solution: Splitting the Pirate Loot

Solution for the 3-Partition Problem.

We'll cover the following

## Solution

Let’s denote $v_1 + v_2 + ··· + v_i$ as sum$(i)$. Splitting the set of $n$ items evenly into three parts is possible only if their total value is divisible by three, i.e., sum$(n) = 3V$, where $V$ is an integer. Then, we need to partition $n$ numbers into three parts where the sum of numbers in each part is equal to $V$. Instead of partitioning all $n$ items, let’s try to solve a smaller problem of partitioning the first $i$ items into parts of value $s_1, s_2,$ and $sum(i) − s_1 − s_2$. We define $split(i,s_1,s_2) =$ true if such partition is possible (and false, otherwise) and note that the pirates can fairly split the loot only if $split(n,V,V)=$ true.

Stop and think:

Given the first five items

$\boxed{3}\boxed{6}\boxed{4}\boxed{1}\boxed{9}$

$split(5,4,13) =$ true.

Find all other values $split(5,s1,s2)$ equal to true.

Imagine that you have already constructed the binary two-dimensional array $split(i−1,s_1,s_2)$ for all possible values $0≤s_1 ≤V$ and $0 ≤ s_2 ≤ V$ . Can you use this array to construct the array $split(i,s_1,s_2)$?

Assume that $split(i,s_1,s_2) =$ true—that is, we can split the first $i$ numbers into three parts such that the sum of numbers in the first part is $s_1$ and the sum of numbers in the second part is $s_2$.

• The $i$-th number belongs to the first part. Then $v_i ≤ s_1$. By taking it out of the first part, we will partition the first $i − 1$ numbers into three parts such that the sum of the first two parts is $s_1 − v_i$ and $s_2$, that is, $split(i − 1, s_1 − v_i , s_2 ) =$ true.

• The $i$-th number belongs to the second part. Then $v_i ≤ s_1$. Similarly to the previous case, $v_i ≤s_2$ and $split(i−1,s_1,s_2−v_i)=$ true.

• The $i$-th item belongs to the third part. Then, $split(i−1,s_1,s_2)=$ true. This way, we compute the value of $split(i,s_1,s_2)$ by looking at $split(i−1,s_1−v_i,s_2)$, $split(i−1,s_1,s_2−v_i)$, and $split(i−1,s_1,s_2)$.

The base case for this recurrence relation is: $split(0,0,0) =$ true and $split(0,s_1,s_2)=$ false if $s_1+s_2 >0$.

$Split(v_1,\ldots,v_n)$:
if $v_1 +\ldots+v_n$ is not divisible by $3$:
return false
$V ←(v_1+\ldots+v_n)/3$
$split ←$ three-dimensional array of size $(n + 1) × (V + 1) × (V + 1)$
initialize all elements of $split$ to false
$split[0][0][0] ←$ true
for $i$ from $1$ to $n$:
for $s_1$ from $0$ to $V$:
for $s_2$ from $0$ to $V$:
$split[i][s_1][s_2] ← split[i − 1][s_1][s_2]$
if $s_1 ≥ v_i$:
$split[i][s_1][s_2] ← split[i][s_1][s_2]$ OR $split[i −1][s_1 −v_i][s_2]$
if $s_2 ≥ v_i$:
$split[i][s_1][s_2] ← split[i][s_1][s_2]$ OR $split[i − 1][s_1][s_2 − v_i]$
return $split[n][V ][V ]$

The running time is $O(nV^2)$.

## Code

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