# $k$-way number contiguous partitioning

Given a set $$S$$ of $$n$$ positive integers $$S=\{a_1,\ldots,a_n\}$$, can we partition $$S$$ into $$k$$ subsets of equal sum such that each subset has contiguous elements from $$S$$?

Here, a contiguous subset is in the form $$\{a_i,a_{i+1},a_{i+2},\ldots\}$$ for some $$i$$. For example, with $$S=\{3,6,2,1\}$$, possible contiguous subsets are $$\{3\}$$, $$\{3,6\}$$, $$\{3,6,2\}$$, $$\{6,2,1\}$$, etc.

Is this variant of $$k$$-wat number partitioning NP-hard?

The problem is in $$\mathsf{P}$$ (and is not trivial), hence it is $$\mathsf{NP}$$-Hard if and only if $$\mathsf{P} = \mathsf{NP}$$.

In particular, you can design an easy linear-time greedy algorithm by observing that the sum of the numbers in each set of the partition must be exactly $$T =\frac{1}{k} \sum_{i=1}^{n} a_n$$. Since all $$a_i$$ are integers, the answer can only be yes if $$T$$ is an integer. Moreover, since all $$a_i$$ are positive, either there is no index $$j$$ such that the elements in $$\{a_1, a_2,\dots, a_j\}$$ sum to $$T$$, or such a $$j$$ is unique. In the latter case $$\{a_1, a_2,\dots, a_j\}$$ must be one of the sets of the partition, hence you can select it and repeat the above argument starting form $$a_{j+1}$$.

Here is the pseudocode of an iterative implementation of this algorithm, where a[i] represents $$a_i$$:

T = a[1] + a[2] + .... + a[n]
if T%n != 0:
return false

T = T/k              //target sum of each set of the partition
sum = 0              //sum of the elements in the current set of the partition
for i = 1, ..., n:
sum = sum + a[i]
if sum > T:        //no way to create the next set with sum T
return false

if sum = T:        //we found the next set of the partition
sum = 0

return true