This is a note for Pisinger’s balancing algorithm for subset sum [1]. Let $\mathcal{S}$ be the set of all subset sums of $S$. The subset sum problem, the input is $S\subset \mathbb{N}$, and we are interested in checking if $t\in \mathcal{S}$.

We define a variation of the subset sum problem. The balanced subset sum problem. In this problem, we are given a vector $v$ of integers(does not have to be positive). We let $M=\Vert v{\Vert }_{\infty }$. We are interested in find a subset that sums to $t\in [M]$.

We partition $S$ into $A=[-M..0]\cap S$ and $B=S\setminus A$. We also define $A_i=\left\{a_1,\dots ,a_i\right\}$ and $B_i=\left\{b_1,\dots ,b_i\right\}$.

A set is balanced by the following recursive definition. Let $S$ be a set.

• $S=\varnothing$ is balanced.
• $\Vert S{\Vert }_1>t$, then $S\cup \left\{a\right\}$ is balanced, where $a\in A$.
• $\Vert S{\Vert }_1\le t$, then $S\cup \left\{b\right\}$ is balanced, where $b\in B$.

Consider a set $T$, such that $(i,j,k)\in T$ if and only if $k$ is a subset sum of $A_i\cup B_j$. Certainly, we are interested if $(|A|,|B|,t)$ is in $T$. However, the state space is already $O(n^{2}M)$, which is no better than the standard dynamic programming algorithm.

There is a nice dominance relation. If $(i,j,k)\in T$, then for $(i^{\prime },j^{\prime })\ge (i,j)$, we have $(i^{\prime },j^{\prime },k)\in T$. We can ask for each $k$, what are all the minimal $(i,j)$ pairs where $(i,j,k)\in T$. Such value will be $g(j,k)$. Formally, $g(j,k)=\min \left\{i|(i,j,k)\in T\right\}$, one can see that $g(j,k)\ge g(j+1,k)$. Also, we know the solution corresponding to $g(j,k)$ must contain $a_{g(j,k)}$ as an element.

One can get a recurrence relation for $g$ as below.

$$g(j,k)=\min \{\begin{array}{ll}g(j-1,k)& \\ g(j-1,k-b_j)& \text{if }k-b_j\le t\\ i& \text{if }k-a_i>t\text{ and }i>g(j,k-a_i)\end{array}$$

Fix a $k$ and $j$, let $i$ to be as small as possible, such that there is $A_i^{\prime }\subset A_i$ and $B_j^{\prime }\subset B_j$ such that $A_i^{\prime }\cup B_j^{\prime }$ is balanced and sums to $k$. Note that $a_i\in A_i^{\prime }$.

We obtained $A_i^{\prime }\cup B_j^{\prime }$ by inserting an element in $B$ or $A$ to another balanced set. If the inserted element is in $B$, but not $b_j$, then we know $i=g(j-1,k)$. If it is $b_j$, then $i=g(j-1,k-b_j)$. If the last inserted is $a_i$, then $g(j,k)=i$. Note we observe in this case, $g(j,k-a_i)<i$. A direct dynamic programming implementation seems to imply a $O(n^{2}M)$ time algorithm, since there does not seem to be a quick way to obtain $i$.

On the other hand, if we think bottom up instead of top down, we can obtain a better result. Below is the algorithm.

The value $D[j,k]$ eventually equals $g(j,k)$. Note we can argue the running time is $O(nM)$, since for each fixed $k$, the final for loop can ran at most $n$ times. It is frustrating that the DP algorithm cannot be inferred directly from the recurrence relation. Indeed, we mainly obtained this through the fact that we can prune the search space if we start bottom up, which is unclear from the recurrence relation.

References