0

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. 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
Community
  • 1
  • 1
Satish Patel
  • 1,784
  • 1
  • 27
  • 39
  • 1
    possible duplicate of [Subset Sum algorithm](http://stackoverflow.com/questions/4355955/subset-sum-algorithm) – Leeor Feb 07 '14 at 07:04

2 Answers2

1

You're trying to solve the 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.

Simeon Visser
  • 118,920
  • 18
  • 185
  • 180
  • One thing is to be noticed that I do not need to consider continuous sub array. – Satish Patel Feb 06 '14 at 16:44
  • 1
    @SatishPatel that's the point, If it was continious, it wouldn't be np-complete - a brute force could solve it in O(n^2). For non-continious, this is basically a *set*, and the problem is NP-Complete. – amit Feb 06 '14 at 16:59
  • SImeonVisser - there is an optimal algoritm, there is no known *polynomial* optimal algorithm. – amit Feb 06 '14 at 16:59
  • @amit: that's right, thanks for the correction (answer updated). – Simeon Visser Feb 06 '14 at 17:09
0

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.

Vikram Bhat
  • 6,106
  • 3
  • 20
  • 19