This is a follow up of #4906.
Please review commit-by-commit:
- First commit: The test case is supposed to verify that input pruning works. However, for inputs
[100] * 2, [10] * 12and a target value of 221 the old code as well as the new code always return[100] * 2, [10] * 3, regardless of the number of iterations, etc. To actually test pruning, one needs a sufficient amount of "big coins" so that the random approximation misses at least one big coin even if iterations=1000 (default). Thus, "smaller coins" get added by the algorithm. (But the algorithm does not yet know they are not sufficient and will later be useless, after executing the second pass) - <strike>Second commit: Use
clang-formatbecause the code style is really messed up here. (Reminder to use ?w=0 flag on GitHub to disable white space diff) // moved to a later pull