0
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.