In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$. The problem can be solved by dynamic programming in time $O(n T)$: for every $i\in\{1,\ldots,n\}$ and $j\in\{1,\ldots,T\}$, we compute whether it is possible to attain a sum of exactly $j$ using the inputs $x_1,\ldots,x_i$.
Suppose that, instead of finding a subset of sum exactly $T$, we only ask if there is a subset of sum between $T$ and $T+k n$, for some fixed integer $k$. Initially, I thought that this could be done faster: round down each input $x_i$ to the nearest multiple of $k$. The inaccuracy for each input is at most $k$, so the cumulative inaccuracy is at most $k n$. Now, we have to consider only $j\in\{1,\ldots,T\}$ which are multiples of $k$, so the run-time is in $O(n T / k)$. However, this solves a slightly different problem:
- If there is a subset with sum $T$, then return a subset with sum in $(T- k n, T)$;
- If there is no subset with sum between $T$ and $T+ n k$, then do not return a subset with sum $T$.
Is there an algorithm to decide whether there is a subset with sum in $\{T,\ldots, T+kn\}$, asymptotically faster than $O(n T)$, for example, in time $O(n T / k)$?
