The subset sum problem [1] is known to be NP-hard with the fastest known algorithm having runtime complexity of $O(2^{0.3113n})$ [2]. I'm wondering if a better algorithm exists for a particular variation, and also if the problem is still NP-hard. The variation is just 2 changes from the original problem:
- Restrict the numbers in the set to positive integers (as apposed to positive and negative). Note the problem is still NP-hard if this is the only change to the original, as claimed in wikipedia but there is a dynamic programming algorithm that gives $O(nt)$ [3] where $n$ is the set size and $t$ is the target sum. The same paper says this variation is NP-Complete.
- The size of the subset is fixed
If the size of the set is $n$ and the subset $m$ then a brute force search finds all combinations and checks the sum. There are $n\text{C}m=\frac{n!}{(n-m)!m!}$ possible combinations, which is ~$O(n^m)$ time complexity. I was unable to find any research or other stack posts that talks about this specific variation so if anyone can point me in the right direction that would be amazing!
The problem with arbitrary subset size is easily reduced to problem with known subset size. Assume you have $n$ total elements: $A = \{a_1, \ldots, a_n\}$ and your target is sum $M$. Let $X_n$ be multiset $\{1, 1, \ldots, 1, 2, 3, \ldots, n\}$ - $n$ ones, and also each number from $2$ to $n$. Problem "does $\{a_1 n^3, \ldots, a_n n^3\} \cup X$ has a subset of size $n + 1$ with size $M n^3 + n$" is subset-sum problem with known subset size, and it has a solution iff original subset sum problem (with set $A$ and sum $M$) has a solution of any size.
Indeed, if you have a solution of original problem of size $k$, then you can add $n + 1 - k$ elements from $X_n$ that sum to $n$, and get solution of new problem.
If you have a solution of new problem, dropping elements from $X_n$ gives you solution to the original problem.