Given n integers a1,a2..an and some integer S. To test whether there exists xi belongs to {0,1} such that:
**S = Summation(xi*ai) [i=0 to n]**
Test whether when using (x1,x2,..xn) := (0,0,..,0) in the above eqn, this would work. Then continue with testing (x1,x2,....,xn) :=,(0,0,0,...1), etc., until finally testing (x1,x2,....xn) := (1,1,.....1). If the above eqn is satisfied for one of these tests, then return True, else False.
1) Analyze the time complexity? 2) Does the algo take polynomial time?
There are $2^n$ integer of $n$ bits, and computing one sum is a linear-time operation.
Hence for the whole procedure, in the worst case $$O(n2^n).$$
This isn't polynomial.
Indeed, for any degree $d$, you can find a value of $n>2d$ such that
$$n^d<2^n,(n+1)^d<2^{n+1},(n+2)^d<2^{n+2}\cdots,$$
as the ratio
$$\left(\frac{n+1}{n}\right)^d<\left(1+\frac1{2d}\right)^d<e^{1/2}<2.$$