What could be the complexity class of the following problem:  Given a positive integer $K$, a positive integer $d$ (say $2$) and a set $S$ of all non-negative integers less than $K$ find a $S' \subset S : \sum{S'} = K$ such that the elements of $S'$ form an arithmetic series with difference $d$ and $a = x_1$. So $S' = \{x_1, x_2 ..., x_n\}$ $: x_{i+1} = x_i + d$ for $2 \le x_i \le n$.The problem is in NP, since given a solution set $A$ it is possible to check in polynomial time if $\sum{A} = K$.The regular [0,1] Knapsack Problem and Subset Sum problem are NP complete and initially I figured this being similar would also be NP complete. However it differs since there is no relationship between the elements of a solution set of a Subset Sum problem. I was also unable to work out a reduction of any known NP-Complete problem to this problem.The constraint on the solution set in the problem does not make it solvable in polynomial time. At best I can work out pseudo-polynomial time algorithms to solve this and the time blows up as K increases. Am I right in suspecting this might be an NP-indeterminate problem or am I missing something?PS: This is not homework. I am new at this and if this is not the right place for this question please advise and I shall move it. Thanks.EDIT: After the discussions in the comments below I am providing a few examples towards what I am working on.The above problem is trivial for the case where $d = 1$ and $n = 2$ for all $K$. It is easy when $K$ is even and for $d = 2$ and $n = 2$. I have been working on cases where $d = 2$ and $d = 4$ for $n \ge 3$ and didn't realise this.For the case $K$ odd and $d = 2$, say $K = 65$ and I have $S = \{1,2,...,64\}$ and $S'= \{9,11,13,15,17\}$. The best algorithm I have for this takes time proportional to $\sqrt{K}$ and is thus exponential as $K$ grows.For $K$ even, $d = 2$ and $n \ge 3$, say $K = 24$ I have $S'= \{3,5,7,9\}$.I have found that when $K$ is odd or even then $|S|$ is odd or even respectively. I am trying to see if I can get a better algorithm to determine $S'$ or if I should concentrate elsewhere.
Complexity class of a subset problem similar to subset sum
np hardness;complexity classes;subset sum
With some basic arithmetic, we can reduce this to a question about a two-variable Diophantine equation.Based upon your comments, it sounds like $d$ was intended to be given as input.  Now the question is just: can we choose $x_1 \ge 1$ and $n$ such that $x_1 + (n-1)d < K$ and such that the arithmetic sequence $x_1,x_1+d,x_1+2d,\dots,x_1+(n-1)d$ sums to $K$.It is easy to compute the sum of this arithmetic sequence.  By the Gauss formula, it sums to$$n x_1 + dn(n-1)/2.$$So, given $K,d$, we want to find a solution to the equation$$n x_1 + dn(n-1)/2 = K$$where $x_1,n$ are positive integers and where $x_1+ (n-1)d < K$.You can view this as a diophantine equation in two variables $x,y$ of the form$$2xy + \alpha x^2 + \beta x + \gamma = 0,$$where $\alpha,\beta,\gamma$ are integer constants given in advance and there is an additional linear inequality on $x,y$.  (Here I made the replacement $x=x_1$, $y=n$.)  I don't know if this problem has a nice solution.One thing we can say is that $n$ must be a divisor of $2K$, since we know$$2nx_1 + dn(n-1) = 2K,$$and the left-hand side is divisible by $n$.  Therefore, if you know the factorization of $2K$, and if it doesn't have too many different prime divisors, you could try enumerating all divisors of $2K$ as the candidate values of $n$, and then for each candidate value of $n$, solve for $x_1$  and see if it yields an integral solution.  However, in general this will not be efficient: it gives an algorithm that is efficient in the average case but runs in exponential time in the worst case.