Subset Sum

From Algorithmist

This is a stub or unfinished. Contribute by editing me.

There are traditionally two problems associated with Subset Sum. One is counting the number of ways a list of $n$ numbers make up a given integer. This is also referred to as the Coin Counting problem. (We will call this Problem C for this article.) The other is figuring out if a subset of a given list of integers can sum to a given integer (usually 0). This is, in a way, a special case of the knapsack problem. (We will call this Problem K for this article.)

[edit] Problem C (Coin Counting)

The problem can be defined as: Given a set (or list) of $n$ numbers $a_1, a_2, \ldots, a_n$ , how many solutions does $k_1a_1 + k_2a_2 + \ldots + k_na_n = T$ have (where $k i > = 0$ for all $i$ )?

Let $c (i, j)$ be the number of ways to sum to $j$ using the subsequence $a_1, a_2, \ldots, a_i$ , then the recurrence is simply:

$c (i, j) = c (i - 1, j) + c (i - 1, j - a i)$

where

$c (0,0) = 1$

This problem is often asked as a variation of such: Given 1c, 2c, 5c, and 10c pieces, how many ways can you make a dollar?

[edit] Problem K (Simplified Knapsack)

This problem can be thought of as a more specific version of Problem C. It can be defined as: Given a set (or list) of $n$ numbers $a_1, a_2, \ldots, a_n$ , is there a solution such that $k_1a_1 + k_2a_2 + \ldots + k_na_n = T$ (where $k i > = 0$ )? This is basically a decision variation on Problem C, and can be solved similarly.

The recurrence is essentially:

$c( i, j ) = c( i - 1, j ) \or c( i - 1, j - a_i )$