2026-10-09
subset_sums.cpp
#include <vector>
std::vector<int> subset_sums(const std::vector<int>& a) {
}
整数の列 a のすべての部分集合について要素の和を求め、std::vector<int> に並べて返す subset_sums を書いてください。添字 mask の位置には、mask のビット i が立っている a[i] の和を置きます。a が空なら、空集合の和 0 だけを持つ列を返します。かかる時間は、部分集合の数に比例するようにします。
入力例 1
subset_sums({3, 5})
出力例 1
{0, 3, 5, 8}
入力例 2
subset_sums({1, 2, 4})
出力例 2
{0, 1, 2, 3, 4, 5, 6, 7}
入力例 3
subset_sums({})
出力例 3
{0}
Reference
#include <bit>
#include <cassert>
#include <vector>
std::vector<int> subset_sums(const std::vector<int>& a) {
std::vector<int> sum(1u << a.size());
for (unsigned mask = 1; mask < sum.size(); ++mask)
sum[mask] = sum[mask & (mask - 1)] + a[std::countr_zero(mask)];
return sum;
}
参考実装は、mask の和を、mask から要素を1つ除いた集合の和から求めます。mask & (mask - 1) は mask の一番下の立っているビットを消した値で、消したビットの位置は std::countr_zero(mask) で分かります。mask が 0b110 なら、0b100 の和に a[1] を足します。
mask & (mask - 1) は mask より小さいので、mask を小さい順に回せば、使う和はいつも計算済みです。1つの mask につき足し算は1回なので、全体の時間は部分集合の数に比例します。部分集合ごとに全ビットを調べて足す書き方では、要素数の分だけ余計に時間がかかります。
掲載したのは参考実装で、唯一の正解ではありません。{0} から始めて、要素を1つ加えるたびに、それまでの各和にその要素を足したものを後ろへ付け足していく書き方でも、同じ順番の列ができます。