

























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。