Re: Using a list as a variable

*To*: mathgroup at smc.vnet.net*Subject*: [mg67077] Re: Using a list as a variable*From*: "J Siehler" <jsiehler at gmail.com>*Date*: Fri, 9 Jun 2006 01:06:38 -0400 (EDT)*References*: <e68qc9$d2i$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Bonny Banerjee wrote: > I would like to use a list (or set) as a variable. I am working on the > Subset-Sum problem. Given a set S of integers, the goal is to find a subset > of S (say Q) whose elements add to a given integer x. Well, the brute force way to find them is like this: SubsetSum[s_, x_] := Select[Subsets[s], Total[#] == x &] ex = {5, 8, 12, 1, 3, 4, 1, 10} SubsetSum[ex, 10] This finds all sets with the desired sum but obviously takes exponential time in the size of set S. There is a better but more complicated exponential-time algorithm for subset-sum, but there is no subexponential algorithm known. If you really want it to just return one subset - the first one it finds - then you can do this: SubsetSum[s_, x_] := Select[Subsets[s], Total[#] == x &,1]