The Art Gallery Guardian

Subset sum of elements sum to σ\sigma

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

In this case, the subset sum problem can be solved in O(σlog2σ)O(\sigma \log^2 \sigma) 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 σ/4\sigma/4 and 3σ/43\sigma/4, and solve each recursively then take the Minkowski sum. One can analyze this and get O(σlog2σ)O(\sigma \log^2 \sigma) 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.