Subset sum into a consecutive range vs. standard subset sum

Question

The following problems live in integer domain.

I want to find a subset of $\{x_0, x_1, \ldots, x_{n-1}\}$ such that the subset's elements sum to any number in a prescribed interval $[X,X+k]$, $k\geq 1$.

We call the above problem A.

An obvious approach is to solve $k+1$ standard subset sum problems with targets $X, X+1,\ldots,X+k$ . I would be satisfied once my algorithm finds a solution to any of these problems.

Now I am wondering, does there exist a single standard subset problem B: $\{y_0,y_1,\ldots,y_{m-1};Y\}$ where $Y$ is the target, such that if I solved B, I equivalently solved A, additionally, the conversion from B's solution to A's solution is fast, preferably in linear time.

To make it simpler, I am only considering $k=1$.

Thank you!

Answer 1

This answer assumes that a Yes instance of your problem with elements $x_0,\ldots,x_{n-1}$ and targets $[X,X+1]$ is one in which there is a subset summing to either $X$ or $X+1$.

Given an instance of your problem with elements $x_0,\ldots,x_{n-1}$ and targets $[X,X+1]$, construct an instance of subset sum with elements $x_0,\ldots,x_{n-1},1$ and target $X+1$. You take it from here.