Smallest Sum Not Present In An Array

INPUT :
An array "A" of size "n".

OUTPUT :
The smallest integer that cannot be represented by the sum of any subset of "A".
E.g. if A = {1, 1, 1, 1}, output = 5; if A = {1, 2, 3, 4, 5}, output = 16

BRUTE FORCE METHOD :
The simplest and possibly the worst method would be to find out all the subsets of A and store each's sum in a Hash Map, then keep an integer i starting from 1 and check every time whether any sum equals to i. This method, is not only inefficient in nature, but also can be unsolvable in the sense that it can be, in worst cases, a NP-Complete problem .

PRE-REQUISUTE :
Before we actually look into our algorithm, let us do a little background. If someone asks you to give a list of numbers that can, with the sum of any of its sub-sets, give a result upto 2^k-1, what numbers do you choose? It is proven mathematically that you need a minimum of k numbers. And each of these numbers is a power of 2. 

So, if given k numbers, all subsequent powers of starting from 1; we can form all numbers from 1 to 2^k, from them. For example, an array {1, 2, 4, 8, 16} can be used to form all numbers from 1-31. This property forms the basis of Binary Number System. Thus, a 5 bit binary number can represent upto 2⁵-1 = 31 i.e. in total, 32 numbers.

OUR APPROACH :
We first sort the array in ascending order. Using the property mentioned above, we assume the entire array to be consisting of powers of 2 or, since its the decimal system, consisting of only consecutive numbers. If our assumption is true and the array indeed consists of only powers of 2 or consecutive integers, then the least number will be 2ⁿ-1, where n is the length of the array. If our assumption fails at any point, then we have found the "gap" in the sequence and the sum of all elements uptill that point is our answer.

We first sort the array in ascending order. We keep a pointer "i" such that "i" traverses the given array A. We also keep a variable "sno" which is the smallest sum initialized at 1. Then we check whether "sno" is lesser than A[ i ], if it is, then we print "sno". Otherwise, we increment "sno" by A[ i ].
 
Algorithm SmallestSum(A)

1. QuickSort(A);
2. sno = 1, i = 1;
3. Traverse A
4.          if(sno >= A[ i ])
5.                 sno += A[ i ];
6.           else return sno;
   

The Java implementation of QuickSort can be found here . The Java implementation of the algorithm is as follows: Note that, ignoring the time efficiency of QuickSort, the algorithm executes in O(n) time. Also note that, since we have extended the logic behind Binary Number System and negative numbers cannot be represented by this system (they are usually represented in sign-magnitude form, wherein the magnitude is always positive. Even the 2's complement form is just a positive number taken with different meaning, e.g. 1110 is either +15 or -2 in 2's complement form), our algorithm will not work for negative numbers. If you find any algorithm which does work for negative integers too, feel free to provide a link in the comments.