Reconsidering the Subset Sum Problem

In the previous chapter, we discussed the subset sum problem, which we saw possessed exponential complexity in the worst cases. Let's consider the two ways this problem can be expressed – in terms of the relative difficulty of finding a solution and verifying the validity of a solution.

Let's consider the problem of verifying the validity of a solution:

Set    —> { 2 6 4 15 3 9 }

Target —> 24

Subset —> { 2 6 4 }

Sum = 2 + 6 + 4 = 12 

FALSE

Subset —> { 2 6 15 3 }

Sum = 2 + 6 + 15 + 3 = 24

TRUE

Subset —> { 15 9 }

Sum = 15 + 9 = 24

TRUE

Subset —> { 6 4 3 9 }

Sum = 6 ...