SumOfSubsets ( ) i, weightSoFar, totalPossibleLeft (promising ( )) //may lead to solution if i then if ( S ) weightSoFar == then print 1 ] to ] //found solution include[ include[ i //expand the node when < S else weightSoFar include [ + 1 ] = including i "yes” //try sumOfSubsets ( + 1, i + 1], weightSoFar + w[i - + 1] ) totalPossibleLeft w[i include [ + 1 ] = //try excluding i "no” sumOfSubsets ( + 1, , i weightSoFar - + 1] ) totalPossibleLeft w[i boolean promising (i ) ≥ 1) return ( + S) && weightSoFar totalPossibleLeft ≤ ( S + 1] weightSoFar == || weightSoFar + w[i S ) Prints all solutions! Initial call sum Of Subsets (0, 0, ) n ∑ w i =1 i
SumOfSubsets ( i, weightSoFar, totalPossibleLeft ) if (promising ( i )) //may lead to solution then if ( weightSoFar == S ) then print include[ 1 ] to include[ i ] //found solution else //expand the node when weightSoFar < S include [ i + 1 ] = "yes” //try including sumOfSubsets ( i + 1, weightSoFar + w[i + 1], totalPossibleLeft - w[i + 1] ) include [ i + 1 ] = "no” //try excluding sumOfSubsets ( i + 1, weightSoFar , totalPossibleLeft - w[i + 1] ) boolean promising (i ) 1) return ( weightSoFar + totalPossibleLeft ≥ S) && ( weightSoFar == S || weightSoFar + w[i + 1] ≤ S ) Prints all solutions! Initial call sum Of Subsets (0, 0, ) n ∑ w i i =1