# Can this relaxed subset-sum problem be solved with a smaller dynamic program? [closed]

Cross-post from CS.SE

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)$$?