Following is an interview question asked by 'Amazon' to me. I still haven't come up with a optimized solution. 

**Problem Statement:**  

Given an unsorted array of integers n. **Return 'true' if the addition** of any integers from that array **matches** with the **target value** else **return false**. 

**Note:** 

```
   1)'n' could be 1000 or 10,000.
   2) Target value could be 'negative'
   3) It may be addition of any 'k' integers (not only two) , where k<=n.  

```

**Test Condition:**

```
    i/p:- Array A[]= {6,7,3,0,12,-5,-6,100}
    Target =  8
    o/p:- TRUE        
As, 6+7+(-5)=8

```

If we try to do it linearly or normally it will take **O(2^n) time complexity**.  

So I am looking for any method or algorithm which will optimized this problem more. 

Thank you in advance!