Dynamic Programming for the Subset Sum Problem

The subset sum problem is a basic problem in the field of theoretical computer science, especially in the complexity theory. The input is a sequence of positive integers and a target positive integer. The task is to determine if there exists a subsequence of the input sequence with sum equal to the target integer. It is known that the problem is NP-hard and can be solved by dynamic programming in pseudo-polynomial time. In this article we formalize the recurrence relation of the dynamic programming.ArticleFORMALIZED MATHEMATICS 28(1) : 89-92(2020)journal articl