# A dynamic program to decide whether the solution is in a given range

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

• Cross-posted: cstheory.stackexchange.com/q/51082/5038. Please do not post the same question on multiple sites.
– D.W.
Feb 10, 2022 at 6:36
• This is not a dynamic programming solution as the title suggests, but there is a near-linear $O((n + t) \mathrm{poly} \log (n + t))$ time randomized algorithm for the subset sum problem [1]. [1]: Karl Bringmann, A near-linear pseudopolynomial time algorithm for subset sum, SODA 2017 Feb 10, 2022 at 13:15
• @pcpthm interesting link, thanks! But it is still worse than $O(n T/k)$ when $k$ is large. Feb 10, 2022 at 13:23
• @D.W. The policy in cstheory.SE is "Crossposting is permitted after a week has passed without a satisfying answer elsewhere". For this question, almost two months have passed, so I thought it was OK. I am sorry if I mis-interpreted the policy. Feb 12, 2022 at 16:40
• Yes, that's part of the CS Theory.SE policy, but not the CS.SE policy. Cross-posting requires the OK of both communities. Please note that the CS Theory.SE policy also requires cross-linking both ways and updating both questions based on answers and comments received on the other site, which has not been followed here.
– D.W.
Feb 13, 2022 at 0:15

Dynamic programming solves the problem in $$O(\sum v)$$, where $$\sum v$$ is the sum of item sizes. The subset sum problem is trivial if the item sizes are small and only gets hard when the item sizes grow.
Imagine I ask you to decide whether there exists a subset with sum $$T \leq sum \leq T+d$$. And in addition I guarantee there is no subset with $$T < sum . Then your problem is to decide whether there exists a subset with sum exactly $$T$$ or exactly $$T+d$$.
• I am not sure I understand the last argument. Do you say that adding informatiom (guarantee) cannot make the problem harder? But with the additional information, maybe the original problem (decide whether there exists a subset with sum exactly $T$, assuming there are no subsets with $T < sum < T+d$) is easy? Dec 17, 2021 at 13:22