I'm trying to understand the approximate polynomial time algorithm for subset sum problem at Wikipedia, but I stuck at the pseudocode's 3rd line:

let T be a list consisting of xi + y, for all y in S

What does this line mean? What is x, and how do I create the correct T list?


Taken from the previous section:

The problem can be solved in pseudo-polynomial time using dynamic programming. Suppose the sequence is x[1], ..., x[N] and we wish to determine if there is a nonempty subset which sums to zero.

So, it appears that x is the input sequences of numbers, for which you're trying to solve, and thus x[i] is the i'th number in the sequence.

Thus, the list T is a map of S where each element of T is that of S but with x[i] added to it.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.