subset_sum
関数 · 部分和が $C$ になる部分集合が存在するか判定する
bool subset_sum(const std::vector<int> &a_orig, int C);
概要
部分和が $C$ になる部分集合が存在するか判定する
パラメータ
| 名前 | 説明 |
|---|---|
a |
各要素の重み（非負） |
C |
目標の部分和 |
計算量
- 要素数を $N$、
aの最大値を $W$ として $O(NW)$
関連項目
subset_sum_all— $C = \sum a_i$ として、$0$ から $C$ までの全ての $k$ について部分和が $k$ になる部分集合が存在するか判定する