MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

You are given $n$ numbers between $-n$ and $n$, the sum of numbers is $0$. Divide the given sequence on disjoint subsequences in such a way that each subsequence has zero sum. Each element should belong to exactly one subsequence. Maximize the number of subsequences. It is not required that elements in subsequences are consecutive.

It seems the problem is NP-hard (or "Can the sequence be partitioned into $k$ subsequences which all have zero sums?" is NP-complete), but can't prove it.

Example: the maximal number of subsequences for the sequence [2, 0, 1, -1, -1, -1] is 3: [0], [2, -1, -1] and [1, -1].

share|cite|improve this question
this is phrased like HW (imperative tone); might get closed soon. – Suvrit Mar 23 '13 at 22:51
It is not a HW or similar. Maybe my wording is not good. – silentbob Mar 23 '13 at 23:09
Answered on… How to hide the question? – silentbob Mar 24 '13 at 8:15

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.