Subset Sum Problem

Author

Eric W. Weisstein
December 30, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/SubsetSumProblem.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/SubsetSumProblem.html.

©2008 Wolfram Research, Inc. except for portions noted otherwise

Same Sum

<<Combinatorica`

Sort[{Plus@@#,#}&/@Subsets[3]]//ColumnForm

Maximal number of subsets of {1,2,…,n} sharing a sum

Max/@Map[Length,Split/@Sort/@((Plus@@@Subsets[#])&/@Range[10]),{2}]

Number of different sums

Length/@Split/@Sort/@((Plus@@@Subsets[#])&/@Range[10])

Given Sum

With[{M=5},
Collect[Times@@Table[1+x^k y,{k,M}],y]
]//TraditionalForm

Select[GreedyAll[Range[10],5],Max[#]≤1&]

ColumnForm[solns=Table[Select[GreedyAll[Range[5],n],Max[#]≤1&&Plus@@#==3&],{n,12}]]

Length/@solns

Map[Flatten[Position[#,1]]&,solns,{2}]//ColumnForm

Change Problem

American

SeriesCoefficient[(1/(Times@@(1-(x^(#))&/@{1,5,10,25,50}))),{x,0,100}]

Series[(1/(Times@@(1-(x^(#))&/@{1,5,10,25,50}))),{x,0,100}]

CoefficientList[Series[(1/(Times@@(1-(x^(#))&/@{1,5,10,25,50}))),{x,0,100}],x]

FindSequenceFunction[%,n]

(ser=SeriesCoefficient[(1/(Times@@(1-(x^(#))&/@{1,5,10,25,50}))),{x,0,n}])//Timing

FullSimplify[ser,n∈Integers&&n>0]//Timing

Canadian

Series[(1/(Times@@(1-(x^(#))&/@{1,5,10,25}))),{x,0,100}]

SeriesCoefficient[(1/(Times@@(1-(x^(#))&/@{1,5,10,25}))),{x,0,n}]//Timing

SeriesCoefficient[(1/(Times@@(1-(x^(#))&/@{1,5,10,25}))),{x,0,100}]