Is there anyone who can prove or disprove my random-based 18809719 solution of this problem?
Short description:
visited[i] on phase j consists of all possible prefix sums that we could have met by collecting coins from left to right.
Example:
{2, 1} is a set of coins, then
visited[0..3] = {{0}, {0, 1}, {0, 2}, {0, 2, 3}}
Suppose that we are looking for value X in visited[K], if we shuffle input many times , then X is gonna be one of prefix or suffix sums on the way to K. (To consider all Suffixes, simply for every X in answer add K - X to the answer)
The question is how many times do I actually need to shuffle input so that I get all values of X with high probability?