概要
部分和問題は、与えられた整数の多重集合の中に、和が指定された目標値に等しくなる部分集合があるかを問う問題である。最も一般的な判定形式では、目標値を整数 x、入力を整数の有限集合または多重集合 S とし、S の部分集合 T ⊆ S が存在して、その要素の和が x に等しいかを尋ねる。たとえば、S = { -7, -3, -2, 5, 8 } で目標値が 0 のとき、部分集合 { -3, -2, 5 } の和は 0 になる。正の整数だけを扱う場合は、「いくつかの数を足してちょうど x にできるか」という形で表現されることが多く、たとえば S = {1, 4, 6, 7} には 10 に和が等しい部分集合 {4, 6} がある。
変種と関連問題
部分和問題には、いくつかの近い定式化が含まれる。
- 判定版：和がちょうど x になる部分集合は存在するか。
- 最適化版：x を超えない範囲で、x に最も近い和をもつ部分集合を求める。
- 個数を数える版：和が x になる異なる部分集合はいくつあるか（#P 型の問題）。
- 制限付き・非制限付き変種：各要素に個数制限がある場合や、繰り返し利用できる場合。
- 特殊ケース：分割問題（目標 = 全体/2）、ナップサック問題（価値をもつ重み付き問題）、お釣り作成問題。
これらの関係から、部分和問題は組合せ最適化や数論的な判定問題の重要な部分問題となっている。一般的な参考文献は 一般的な参考資料、例データは コレクション を参照できる。
計算量とアルゴリズム
判定問題としての部分和問題は一般に NP 完全であり、すべての入力を多項式時間で解くアルゴリズムは知られていない。ただし「弱い」NP 完全問題であるため、動的計画法により擬多項式時間アルゴリズムが得られる。この計算量は項目数だけでなく入力の数値の大きさに依存し、典型的には O(n·W)（W は目標値または和の大きさ）となる。したがって、数が小さい場合や一進表現のように数値が扱いやすい場合には、実用的に機能する。
よく用いられるアルゴリズム手法は次のとおりである。
- 擬多項式性能を得るための動的計画法（表形式またはビットセット）。
- 集合を二分し、部分和を組み合わせる meet-in-the-middle 法。おおむね O(2^{n/2}) で、n が中程度のとき有効。
- 多くの実例に対する厳密解法で使われる branch-and-bound と枝刈りヒューリスティクス。
- 大規模な実問題に向けた近似法、ヒューリスティクス、または SAT/ILP への還元。アルゴリズム概説は アルゴリズム資源 を参照。
歴史と応用
部分和問題は、計算量理論の初期の発展期から研究されてきた、代表的な NP 完全問題の一つである。資源配分、スケジューリング、暗号、組合せ設計などに実用的な用途がある。歴史的には、ある種のナップサック型暗号系（たとえば Merkle–Hellman ナップサック）は部分和問題に似た構成に基づいていたが、その後いくつかは破られた。これは、組合せ問題を安全性に用いる際の実用上の関心と難しさの両方を示している。歴史的・概説的な資料は さらなる参考 を参照できる。
例、区別、注目点
重要な特殊ケースが分割問題である。多重集合を和が等しい二つの部分に分けられるかを判定することは、全体の半分に等しい和をもつ部分集合があるかを問うのと同じである。解の個数を数える問題は一般にさらに難しく、#P 完全である。また、擬多項式アルゴリズムが存在することは、弱い NP 完全性と強い NP 完全性の違いを説明する際の良い例になる。実用的な解法では、動的計画法に加えて、ビットセットや到達可能和のソート済みリストのような巧妙なデータ構造、さらに meet-in-the-middle のトレードオフを組み合わせ、多くの現実的な入力を効率よく扱う。
単純な定義をもち、他の組合せ的問題とも深く結びついているため、部分和問題は理論的なベンチマークとしても、応用アルゴリズムの構成要素としても中心的な問題であり続けている。