# A variation of the subset sum problem [closed]

The subset sum problem is NP Complete. I was wondering if the following variation can be proved to be NP Complete :

The cardinality of set of integers is $m$. And each element of the set is between $1$ and $m^2$. Repetitions are allowed. The objective is to find a subset that would sum up to a given sum.

This seems to be as hard as the subset sum itself, but i cant come up with a reduction that would prove my conjecture.

• Voted to close as off-topic; not a research-level question. This seems to be a variant that is easy to solve using dynamic programming. – Jukka Suomela May 7 '11 at 14:13
• so solvable using dp implies a polynomial time algorithm right? – AnkurVj May 7 '11 at 15:06
• No, but in this case it is a polynomial-time algorithm. – Jukka Suomela May 7 '11 at 15:56
• I don't know if you have read the FAQ but this site is for research-level questions in theoretical computer science. Please refer to the FAQ for further information about the scope of cstheory. Closing the question as off-topic. – Kaveh May 7 '11 at 20:39