subset_sum_all
関数 · 部分和が $C$ になる部分集合が存在するか判定する
std::vector<bool> subset_sum_all(const std::vector<int> &a);
概要
$C = \sum a_i$ として、$0$ から $C$ までの全ての $k$ について部分和が $k$ になる部分集合が存在するか判定する
パラメータ
| 名前 | 説明 |
|---|---|
a |
各要素の重み（非負） |
戻り値
res[k] == true iff 部分和が $k$ になる部分集合が存在する（$0 \le k \le C$）
計算量
- $O(C \sqrt{C} / 64)$
関連項目
subset_sum— 部分和が $C$ になる部分集合が存在するか判定する