这不是一篇题解，只是偶然发现大多数提交的复杂度都是错的。

其实只是少了一个剪枝：对所有搜索得到的二元组 $(state,sum)$ 去重。

以下记 $N=2n$。

如果不去重，考虑一组数据满足 $a_i=1$。此时前一半中 $sum=i$ 的状态有 $[x^i](1+x+x^{-1})^n=[x^{i+n}](1+x+x^2)^n$ 个，记作 $f_i$。

由于我们是对于每一个后一半的状态，遍历所有前一半与之相等的状态，那么总遍历量为 $\sum_i{f_i^2}$。查一下 OEIS 发现，这个东西是 $O(\frac{3^{2n+0.5}}{2\sqrt{2\pi n}})$ 也就是 $O(\frac{3^{N+0.5}}{2\sqrt{\pi N}})$ 的，其实不比 $O(3^N)$ 的暴力优多少，证明在link。

然而如果去重了，一个粗略的上界是，对于后一半的 $3^n$ 个状态，前一半中最多有 $2^n$ 个状态与之对应，那么就是 $O(6^{\frac{N}{2}})$ 的。此时也能看出，某谷上一堆说复杂度是 $O(3^{\frac{N}{2}})$ 的题解全是瞎扯。

值得注意的是，官方其实还给出了一种 $(1+\sqrt{1.5})^N$ 的做法，奈何我英语不好看不懂。链接是link。