Actually its a topcoder 500pt problem.I was given a vector of positive numbers and i was asked to Find the smallest positive integer X that cannot be obtained as the sum of some (possibly all) elements of S.Size of array is less than 20 and every element fits in integer.
For eg.
{5, 1, 2}
Returns: 4
These are all the positive integers that can be obtained: 1, 2, 3, 5, 6,7,
and 8. (We can obtain 3 as 1+2, 6 as 1+5, 7 as 2+5, and 8 as 1+2+5.)
The smallest positive integer not present in the above list is 4.
I was able to do this question with 458.62pts.But i got TLE in some cases.I know this is O(n*2^n).
My approach
class NumbersChallenge
{
public:
int MinNumber(vector<int>&v)
{
int max=0;
for(int i=0;i<v.size();++i)max+=v[i];
for(int i=1;i<max;i++)
{
int flag=0;
for(int j=0;j<pow(2,v.size());j++)
{
int sum=0;
for(int k=0;k<v.size();k++)
{
if(j&(1<<k))
sum+=v[k];
}
if(sum==i)flag=1;
}
if(flag==0)
return i;
}
}
};
I gave it a thought but could not think of better complexity than this.
