# Subset Sum

 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 ${\displaystyle 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.)

## Problem C (Coin Counting)

The problem can be defined as: Given a set (or list) of ${\displaystyle n}$ positive integers ${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$, how many solutions does ${\displaystyle k_{1}a_{1}+k_{2}a_{2}+\ldots +k_{n}a_{n}=T}$ have (where ${\displaystyle k_{i}\geq 0}$ for all ${\displaystyle i}$)?

Let ${\displaystyle c(i,j)}$ be the number of ways to sum to ${\displaystyle j}$ using the subsequence ${\displaystyle a_{1},a_{2},\ldots ,a_{i}}$, then the recurrence is simply:

${\displaystyle c(i,j)=c(i-1,j)+c(i,j-a_{i})}$

where

${\displaystyle 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?

## 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 ${\displaystyle n}$ positive integers ${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$, is there a solution such that ${\displaystyle k_{1}a_{1}+k_{2}a_{2}+\ldots +k_{n}a_{n}=T}$ (where ${\displaystyle k_{i}>=0}$)? This is basically a decision variation on Problem C, and can be solved similarly.

The recurrence is essentially:

${\displaystyle c(i,j)=c(i-1,j)\lor c(i,j-a_{i})}$

where

${\displaystyle c(0,0)=1}$

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9 Output: True //There is a subset (4, 5) with sum 9. Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to sum. n is the number of elements in set[].

The isSubsetSum problem can be divided into two subproblems …a) Include the last element, recur for n = n-1, sum = sum – set[n-1] …b) Exclude the last element, recur for n = n-1. If any of the above the above subproblems return true, then return true.

Following is the recursive formula for isSubsetSum() problem.

isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) ||
isSubsetSum(set, n-1, sum-set[n-1])


Base Cases:

isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0


## Other variations

There are still other variations and constraints that can be solved similarly. A constraint where ${\displaystyle \forall i\,\,k_{i}\in \{0,1\}}$ is one such example.