部分和問題

n 個の整数 a₁, a₂, …, a_n, とし、それらのいくつかの和（部分和という）を C とする。

この C になるには、 どの整数が足されていたかを求める問題。

すなわち、 C = a₁ m₁ + a₂ m₂ + ... + a_n m_n のとき、 n ビットの (m₁, m₂, …, m_n) を求める問題。

n が大きいと 最新のコンピュータでも 部分和問題を解くことはできません。