# How to check if any subset of a given set of numbers can sum up to a given number

Given a number, say $x$, and a set of numbers made up of only $k$ different numbers, where each of the $k$ numbers is repeated $n_1,n_2,\dots n_k$ times. How do I tell if it is possible to find a subset such that it sums to $x$.

E.g.: $$x=6 , k=3$$ $$S=\{1,2,3,3,2,1\}$$ $$n_1=2, n_2=2, n_3=2$$ $$1+2+3=6$$ so its possible.

All the numbers in the set are square free.

• This is known as the subset sum problem and as far as is known the best algorithms have exponential complexity. Are you interested in a description of searching for a solution by backtracking? Commented Oct 11, 2015 at 16:22
• what if k<=10, is there a better way to do this ? I already know about the subset sum problem, but its not fast enough Commented Oct 11, 2015 at 16:33
• Yes, all the numbers and 'x' are positive, there is one other thing that i forgot to mention, all the numbers in the set are square-free Commented Oct 11, 2015 at 16:34
• It seems odd that you would edit the Question to say the numbers are square-free, but omit that they are nonnegative integers (if I understood correctly). Certainly the only possible sums $x$ will be multiples of the GCD of all your potential summands, so without loss of generality they have combined GCD one. Knowing the underlying set of $k$ values is small helps, but I don't see that being square-free is relevant. Commented Oct 11, 2015 at 16:51
• 've found out how to do it a bit faster, I'm posting it here just in case you want to know how @hardmath: For each of the 'k' different numbers, we will create new summands containing the number 1,2,4,... times until its no longer possible to create new summands, so any number having l*ni as a summand for some 'l' and ni can also be expressed as a sum of these new summands, but now, there will be at most logN summands for each distinct number Commented Oct 16, 2015 at 14:04

There are several studied variations on the Subset Sum Problem. The one described here, at least for arbitrary multisets of natural numbers, is essentially the Bounded Knapsack Decision Problem, where "bounded" refers to the number of items of the ith kind having a bound $n_i$.
It is therefore "believed to be one of the easier $\mathcal{NP}$-hard problems" (Where are the hard knapsack problems?, Pisinger (2003)).
If the algorithms for exactly solving this problem are not satisfactory in performance, then as a fallback one might consider approximate algorithms or probabilistic algorithms. By the first of these alternatives we mean answering a "relaxed" question about whether we can come within a tolerance of the required sum $x$, and there exist polynomial time algorithms (but whose complexity nonetheless depends on the allowed tolerance). See Bounded Knapsack Problem for a detailed analysis (Chapter 3 of the book Knapsack Problems - Algorithms and Computer Implementations by Martello and Toth, 1990).
By probabilistic algorithm we mean a randomized search that has a significant likelihood of finding (within polynomial bounded time) the exact sum $x$ if it is feasible, but may fail to do so (within the time bound) even if a solution exists. For example, simulated annealing is often proposed as a search technique. A recent proposal (Gao, Qui and Cao, 2014) is Estimation of Distribution Algorithms for Knapsack Problem, which has good references to the literature.