Hints : Counting Prefixes Hint 1 ↕ Come up with an O(n) algorithm to compute the answer when the sum of elements is fixed to s. Hint 2 ↕ Stars and Bars would be used to solve the version with a fixed sum.