Problem 6.5 - Subset summing to 0 mod n

**learner** · February 15, 2016, 10:08pm

The problem calls for any subset however the solution provided in the book only addresses contiguous subsets. The example itself has a non-contiguous subset {3, 4, 9}. What is the best algorithm for subset summing for non-contiguous subsets?

**tsunghsienlee** · February 16, 2016, 4:01am

For non-contiguous case, https://en.wikipedia.org/wiki/Subset_sum_problem is the algorithm you are looking for. Of course, it won’t be as fast as the one on the book since it is special case one.

**learner** · February 16, 2016, 7:17am

Is this error already in the book’s errata?

**tsunghsienlee** · February 16, 2016, 5:24pm

This is not an error in fact. The solution in book actually can solve this question but the subset sum algorithm is just a more powerful one with much higher time complexity.

**learner** · February 17, 2016, 8:25am

Sorry - I’m confused. The solution in the book explicitly looks for contiguous elements. It does not consider non-contiguous elements as a solution.