Find minimum sum of set Given a multiset of $N$ numbers  we need to find minimum non negative integer that we can not obtain from the sum of any of its subsets.
EXAMPLE: Let the multiset $S$ be $\{1,1,3,7\}$, we can obtain: $0$ as $(S' = \{\})$, $1$ as $(S' = \{1\})$, $2$ as $(S' = \{1, 1\})$, $3$ as $(S' = \{3\})$, $4$ as $(S' = \{1, 3\})$, $5$ as $(S' = \{1, 1, 3\})$, but it can't return $6$. So, Minimum Sum of $S$ equals to $6$. 
Is their any particular formula for finding it out?
 A: Here is a general $O(|S| \log(|S|))$-algorithm for finite multisets of positive integers:
Sort your numbers $\{a_1,...,a_m\}$ of the multiset in an ascending sequence $a_1\leq a_2 \leq ...\leq a_m$.


*

*If $a_1$ is not $1$, the answer is $1$.

*Otherwise sum the numbers from left to right. Find the first $n$ such that $\sum_{i=1}^na_i+1<a_{n+1}$ Then $ \sum_{i=1}^na_i+1$ is your solution.

*If there is no such $n$, the answer is $\sum_{i=1}^m a_i +1$.



In other words: the minimal number that is not the sum of
  any subset of $S$ is $$\min_{i=1,...,m} \left \{ 0\leq n
 \leq m\sum_{i=1}^n a_n +1 < a_{n+1} \right \}$$ where we add to the
  sequence $a_0 = 0$ and $a_{m+1} = \infty$.

You can show that this is indeed your solution by induction on $m$: 


*

*the first bullet gives you the induction start. 

*Assume that every positive integer $\leq \sum_{i=1}^{m-1}a_i$ can be written as a sum of the entries $a_1,...,a_{m-1}$. 


*

*if $\sum_{i=1}^{m-1}a_i +1 < a_m$, then clearly $\sum_{i=1}^{m-1}a_i +1$ is the answer, because the sequence is sorted.

*if $\sum_{i=1}^{m-1}a_i +1 \geq a_m$, then by adding $a_m$ to any number $\leq a_m$ every positive integer  $\leq \sum_{i=1}^{m}a_i$ can be written as a sum of the entries $a_1,...,a_{m}$. This completes the induction.


