解説

一般的に有名な半分全列挙はソートをする関係で $O(2^{n/2}n)$ になりがちですが、 $O(2 ^ {n / 2})$ で解けるよという話をします。

まず、マージソートなどで有名な話として、ソートされた二つの列をソートされた状態でmergeするのは $O(列の長さ)$ でできます。

C++ですと、std::merge という標準ライブラリがあるので使うのが手っ取り早いです。

さて、ここまでくるとあとはそこまで難しくないです。

半分に分けた列 $V$ について考えましょう。

$S _ {i}$ を $i$ 番目の要素まで、 $2^ i$ パターンが昇順に入った列とします。

ここで $i + 1$ 番目の要素を $S$ に加えた集合を $T$ とすると、この $T$ は昇順です。

二つの列を昇順した状態でmergeするのは上述したとおり、線形でできます。

あとはこれの計算量ですが、

$O(1 + 2+ 4 + \cdots + 2 ^ {|V|}) = O(2 ^ {|V|})$

です。

よって後は尺取りをすれば、 $O(2 ^ {n / 2})$ で解くことができました！

提出コード