An Improved Algorithm for the Subset Sum Problem
子集和问题的改进算法

Due to the importance of the subset sum problem in cryptosystem,in the past two decade,much ellort has been done in order to find techniques that could lead to practical algorithms with reasonable running time. Based on the two-list four-table algorithm ,this paper proposes an improved algorithm for the solution of subset sum problem. To find a solution for the n-element subset problem,the proposed algorithm needs O(2^n/2-g) memory,1≤ε≤n/4,and in O(ε(2^n/2)) time. The theoretic analysis and the computational experiments show that our proposed algorithm can solve the subset problem instances that can‘t be solved before ,thus it is an improved result over the past researches.