Algorithms

Algorithm SumOfSubSet(s,k,r)
// Find all subset of w[1:n] that sum to m. The values of x[j],
// 1 <j<k, have already been determined. s = w[1]*x[1] + ... + w[k-1]*x[k-1]
// and r = w[k] + .. + w[n]. The w[j] are in non decreasing order
// It is assumed that w[1]< m and sum of w[i] > m where i = 1..n
{
	x[k] := 1;
	if( s + w[k] = m ) then Write( x[1:k]); // Subset found
	else if( s + w[k] + w[k+1] <= m ) 
		then SumOfSub( s + w[k], k+1, r-w[k]);
	if( (s+r-w[k] >= m) and (s + w[k+1] <= m )) then
	{
		x[k] := 0;
		SumOfSub( s, k + 1, r - w[k]);
	}
}