2018/07/07 by Zhengjun Cao, Lihua Liu, Cao, Zhengjun +1
Computer Science · Engineering · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Rough Sets and Fuzzy Logic
paper · pdf · doi:10.48550/arxiv.1807.02611
openalex publication_date 2018/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a set (or multiset) S of n numbers and a target number t, the subset sum problem is to decide if there is a subset of S that sums up to t. There are several methods for solving this problem, including exhaustive search, divide-and-conquer method, and Bellman's dynamic programming method. However, none of them could generate universal and light code. In this paper, we present a new deterministic algorithm based on a novel data arrangement, which could generate such code and return all solutions. If n is small enough, it is efficient for usual purpose. We also present a probabilistic version with one-sided error and a greedy algorithm which could generate a solution with minimized variance.