你真的会 01 背包吗？
这是一篇简短的 subset sum through balancing 的介绍。
有 $n$ 个数 $d_i$，满足 $d_i \in [1, D]$。我们希望知道是否存在 $S \subset \set{i|i\in[1,n]}$，满足 $\sum\limits_{i\in S} d_i = V$。
标准的做法是直接做 01 背包，由于总的值域为 $nD$，只能做到 $O(n^2D)$ 的复杂度（可以 bitset 除掉一个 $\log$），不够优秀。
事实上，我们可以略施小计，将值域缩减到 $O(D)$ 级别。
考虑找到一个最大的 $p \in [1,n]$ 满足 $\sum\limits_{i=1}^{p} d_i \le V$。如果 $p = n$ 那么直接判断即可；否则，我们离 $V$ 只相差 $O(D)$。
方便起见，称 $[1,p]$ 为左边，$(p,n]$ 为右边，记 $v=\sum\limits_{i\in S} d_i$。初始时，所有左边物品都被选了，所有右边物品都没被选，$v=v_0=\sum\limits_{i=1}^{p} d_i$。
容易发现，接下来我们只会做两种操作：
- 删去左边选上的物品；
- 选上右边未选的物品。
操作 1 只会在 $v > V$ 时执行，操作 2 只会在 $v < V$ 时执行。容易发现，在所有时刻，$v \in [V-D, V+D]$。
考虑记 $f_{i,j,k}$ 表示目前已经考虑了 $[i,j]$ 内的所有操作，能否使 $v=k$。根据刚才的分析 $k$ 的有效值域是 $O(D)$ 的。
但是这样状态数还是 $O(n^2D)$ 的，考虑优化。一个状态只存 1 bit 太浪费了，注意到一段前缀 $i$ 对应的 $f$ 都是 $\mathtt{true}$，改为记 $g_{i,k}$ 表示右端点操作到 $i$，可以使 $v=k$ 的最大左端点。若无解，则记 $g_{i,k}=0$。
边界情况是 $g_{pos,v_0}=pos+1$。
转移如下：
- $g_{i,j} \gets g_{i-1,j}$ 即：右端点右移一位，并且维持原状；
- $g_{i,j+a_i} \gets g_{i-1,j}$ 即：右端点右移一位，并且将右端点对应物品选上；
- $g_{i,j-a_k} \gets k\ (\text{where }k \in [g_{i-1,j}, g_{i,j}))$ 即：左端点左移，并且删除左端点对应物品。
注意到无需考虑左端点左移并且维持原状的情况；并且如果 $k < g_{i-1,j}$ 则有 $k \to g_{i-1,j-a_k} \to g_{i,j-a_k}$ ，无需重复转移。这也保证了第三种转移的复杂度正确。
综上，我们得到了一种 $O(nD)$ 的 subset sum 问题解法。