Pseudo-polynomial Time Algorithm
The problem can be solved using dynamic programming when the size of the set and the size of the sum of the integers in the set are not too big to render the storage requirements infeasible.
Suppose the input to the algorithm is a list of the form:
- S = x1, ..., xn
Let N be the sum of all elements in S. That is: N = x1 + ... + xn. We will build an algorithm that determines if there is a subset of S that sums to . If there is a subset, then:
- if N is even, the rest of S also sums to
- if N is odd, then the rest of S sums to . This is as good a solution as possible.
Read more about this topic: Partition Problem
Famous quotes containing the word time:
“I am of course confident that I will fulfil my tasks as a writer in all circumstances—from my grave even more successfully and more irrefutably than in my lifetime. No one can bar the road to truth, and to advance its cause I am prepared to accept even death. But may it be that repeated lessons will finally teach us not to stop the writer’s pen during his lifetime? At no time has this ennobled our history.”
—Alexander Solzhenitsyn (b. 1918)