この問題は、部分和問題の上位互換であるため NP 困難であることが分かります。

\(N \le 40\) と \(N\) の値が非常に小さいことに注目しましょう。

解く問題を全探索すると、 \(O(2^N)\) 時間になって TLE してしまいます。
そこで、半分全列挙というテクニックを使います。

1. 数列 \(A\) を要素数が半分になるように 2 つに分けます。これを \(B\) と \(C\) とします。
2. \(B\) からいくつか選んだときの総和としてありえる値を全て列挙し、ソートしておきます。これを \(D\) とします。これにかかる計算量は \(O(N2^{N/2})\) 時間です。
3. \(C\) からいくつか選ぶ選び方を全探索し、 \(B\) と合わせて最大値を求めます。 このとき、最適な \(B\) の要素の選び方は \(D\) を二分探索することで求めることができます。これにかかる計算量は \(O(N2^{N/2})\) 時間です。

これで、全体で \(O(N2^{N/2})\) 時間でこの問題を解くことができます。

回答例 (C++) : https://atcoder.jp/contests/abc184/submissions/18301274
回答例 (Python) : https://atcoder.jp/contests/abc184/submissions/18300926

それぞれのステップを工夫すると \(O(2^{N/2})\) 時間で解くこともできます。

\(B_1, B_2, \dots, B_i\) からいくつか選んだときの総和としてありえる値を全て列挙し、ソートしたものを \(D_i\) とします。 \(D_0 = [0]\) です。
\(D_x\) は \(D_{x-1}\) と、「 \(D_{x-1}\) の全ての要素に \(B_x\) を足したもの」をマージすることで求めることができます。
\(|D_0| + |D_1|+|D_2|+\dots+|D_x| ≤ 1 + 2 + 4 + \dots + 2^x = O(2^x)\) であるため、 \(D_{N/2}\) は \(O(2^{N/2})\) 時間で求めることができます。

\(B\) からいくつか選んだときの総和としてありえる値を全て列挙し、\(C\) からもいくつか選んだときの総和としてありえる値を全て列挙し、それらをしゃくとり法で合わせることで、全体で \(O(2^{N/2})\) 時間でこの問題を解くことができます。

回答例 (C++) : https://atcoder.jp/contests/abc184/submissions/18301551
回答例 (Python) : https://atcoder.jp/contests/abc184/submissions/18301408