To answer the sub-questions you posted on math.stackexchange.com one by one:
What is the difference between the big S
and the small s
? The big S
is a list variable which is initially the list [0]
and is modified over the course of the execution of the code. The little s
is a number that remains constant. Specifically, s
is the number from this question:
Given a set of integers and an integer s, does any non-empty subset sum to s?
But what is S
, anyway? Roughly speaking, S
represents the set of all "useful" sums that we can make using the elements we've seen so far (if I'm not mistaken).
Does "a list with element 0" mean a list containing a single number, which is zero? Yes, that's what that means.
What does y + cs/N < z ≤ s
mean? It means that y + c*s/N < z
and z ≤ s
. So the if
will fail whenever y + c*s/N ≥ z
or z > s
(or both).
And some questions you didn't ask, but which seem likely to come up:
What is N
? N
is the number of elements in the set we are given.
What is xi
? xi
is the i-th element of the set we are given.