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.
 A: 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$.
These decision problems are known to be NP-complete, and unless P=NP, there will be no algorithm that (over general inputs) has better than exponential complexity (exponential in the size of input data, measured by counting bits).  However there is a pseudo-polynomial time algorithm based on dynamic programming, and the distinction is discussed under Knapsack problem — NP-complete despite dynamic programming solution?.
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.
