Solving the Subset Sum Problem with Heap-Ordered Subset Trees

Abstract

In the field of algorithmic analysis, one of the more well-known exercises is the subset sum problem. That is, given a set of integers, determine whether one or more integers in the set can sum to a target value. Aside from the brute-force approach of verifying all combinations of integers, several solutions have been found, ranging from clever uses of various data structures to computationally-efficient approximation solutions. In this paper, a unique approach is discussed which builds upon the existing min-heap solution for positive integers, introducing a tree-based data structure influenced by the binomial heap. Termed the subset tree, this data structure solves the subset sum problem for all integers in time $O(N^3k\log k)$, where $N$ is the length of the set and $k$ is the index of the list of subsets that is being searched.