CODEWITHSUNDEEP
algorithmnp-complete
mocode9
mocode9

Reputation: 239

Come up with polynomial algorithm

Given n checks, each of arbitrary (integer) monetary value, decide if the checks can be partitioned into two parts that have the same monetary value.

I'm beyond mind blown on how to solve this. Is there an algorithm to solve this in polynomial time or is this NP-Complete?

Upvotes: 1

Views: 272

Answers (2)

Abdennacer Lachiheb
Abdennacer Lachiheb

Reputation: 4888

Actually you can solve this in O(n*sum/2) using dynamic programming, first sum up all checks into a varaibel sum, then you can perform dp on the checks values (either take it or leave it or take it) and check at the end if that sum is equal to s/2.

Upvotes: 0

Gene
Gene

Reputation: 46960

Yes it's an NP complete problem. It's a variation of the subset sum problem.

Upvotes: 2

Related Questions