search problem


Subset-sums equality (pigeonhole version) ★★★

Author(s):

\begin{problem} Let $a_1,a_2,\ldots,a_n$ be natural numbers with $\sum_{i=1}^n a_i < 2^n - 1$. It follows from the pigeon-hole principle that there exist distinct subsets $I,J \subseteq \{1,\ldots,n\}$ with $\sum_{i \in I} a_i = \sum_{j \in J} a_j$. Is it possible to find such a pair $I,J$ in polynomial time? \end{problem}

Keywords: polynomial algorithm; search problem

Syndicate content