The Art Gallery Guardian

Subset sum of elements sum to


We assume the input of the subset sum problem is a sequence of positive integers that sums to . We are interested if there is a subsequence sums to .

In this case, the subset sum problem can be solved in time. In fact, it output all possible subset sums in the same running time.

Consider we partition the input into two subsequences, each have sum in between and , and solve each recursively then take the Minkowski sum. One can analyze this and get running time. Notice if at some point, such partition cannot be found, then there is a side with a single huge element, and hence can be solved in constant time.

Posted by Chao Xu on .
Tags: Algorithm.