Find the smallest natural number that can not be written as a sum of elements of S? Given a set of natural numbers $S_1$ , $S$ and a number N .
Specification of sets are as follow .
$$S = \{1,\dots N\}$$
$$S_1\subset S \;and \;S_1=\{b_1,b_2,\dots,b_m\}$$
And $$S' = S\setminus S_1$$
Find the smallest natural n that can not be written as a sum of elements of S'.
Note:
A number can't be used more than once .
e.g. if $S=\{1,2,3\}$ and $S_1=\{3\}$ then $S' = \{1,2\}$ we can't form $4$ using $S'$, so answer is $4$.
Can we design an algorithm to solve this problem  useing the knowledge of set $S_1$  and N?
 A: A possible rather stupid way to do it is to compute the sum $M$ of all elements of $S_1$. Form an array $a$ (filled with zeroes) with the numbers from $1$ to $M-1$. Then compute all the possible sums of elements of $S_1$ (there are $2^N-1$ such sums where $N=\text{Card}\, S_1$, the number of elements of $S_1$) and for each result $i$, put the value $a_i$ to $1$. Once you've done it, the smallest value $i$ such that $a_i=0$ is the searched result. 
There are many ways to improve this algorithm, but that's a start.
If you want to improve, use polynomials and compute the product
$$ P(X)=\prod_{p\in S_1}(1+X^p)$$
The coefficient of $X^k$ in $P(X)$ is actually the number of ways to form $k$ as a sum of elements of $S_1$. So you just have to look for the smallest $k$ such that the coefficient of $X^k$ is zero. This technique does not improve efficiency.
A: EDIT: I just realized how simple this problem is. Here's the solution in Lua:
S={1,1,1,1,5,7,10,25,50,75,100,250,500,1000}
table.sort(S)
x=1
for i=1,#S do
if S[i]<=x then
x=x+S[i]
end
end
print(x)
Starting at x=1, go in ascending order increasing x if the number is less than or equal to x, and stop when it isn't (or when they all are).
ex.given the set {1,1,1,1,5,9,12,31,50,100,300}
1 = 1
2 = 1+1
3 = 1+1+1
4 = 1+1+1+1
5 = 5
...
8 = 5+1+1+1
9 = 9
...
12 = 9+1+1
...
30 = 12+9+5+1+1+1+1
31 = 31
...
49 = 31+12+5+1
50 = 50
...
100 = 50+31+12+5+1+1
...
211 = 100+50+31+12+9+5+1+1+1+1
212 = X (smallest value which cannot be made)
