I was trying to solve a problem which is to verify that if there exist a sub sequence whose sum is equal to a given number. I found this thread [Distinct sub sequences summing to given number in an array](https://stackoverflow.com/questions/17125536/distinct-sub-sequences-summing-to-given-number-in-an-array).
I don't have to solve it for all the possible sub sequence I just need is to verify. What is the most optimal algorithm to verify it.
e.g. `a[]={8,1,2,5,4,7,6,3} and num=18`

```
8+2+5+3 = 18

```
['https://Stackoverflow.com/questions/21608613', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1763475/']
You're trying to solve the [subset sum problem](http://en.wikipedia.org/wiki/Subset_sum_problem) which is known to be NP-complete.

Hence there's no known optimal polynomial algorithm. However if your problem permits certain constraints then it may be possible to solve it elegantly with one of the algorithms provided in the Wikipedia article.
There is a pseudo polynomial Dynamic Programming solution similar to knapsack problem using following analogy :-

> 
> 1. Knapsack capacity W = num
> 2. Item i's weight and cost is same as arr[i]
> 3. Maximize Profit
> 4. if MaxProfit == W then there exists subsequence else no subsequence possible.
> 5. Recontruct solution using DP values
> 
> 
> 

**Note:** So as this can be reduced to knapsack problem hence there is no polynomial time solution yet found.