Dynamic Programing Solution to Subset Sum Problem

Problem: Given a set of integers, find a subset of them which sum to a target value s.

Solution: We can definitely first sort the set, then use some recursive approach to solve the problem. The complexity is expected to be exponential. Here we give a DP approach, though the complexity is also not polynomial.

• First we need to define the state. We have a state function Q(i,k) which means if we can find a subset from the set of integers a1,a2, ..., to ai which sum to k. So Q(i,k) is a Boolean function.
• We have  Q(1,k) = ( a1 == k);  Q(i,k) =  Q(i-1,k)  or  ( ai == k) or  Q(i-1,k-ai).
• Then we just need to fill in the matrix of  Q(i,k). We know 0< i <= the size of the set. For k, we have   N=< k <=P, where N is the sum of all the negative integers in the set and P is the sum of all the positive integers in the set.