Talk:Subset sum problem

I ran into some unanticipated implementation issues the last time I tried to create a task, so I'd like to request feedback on this one before promoting it even though it seems straightforward enough to me.

Sluggo 15:58, 1 January 2012 (UTC)

1) Why the words? 2) Caution about trying all subsets being "infeasible" seems superfulous. The problem is NP-complete, so for any algorithm, it's easy enough to construct a data set that will run (practically) forever or exhaust memory. --Ledrug 08:16, 2 January 2012 (UTC)

Thank you for your comments. My rationale is as follows. 1) Any practical application in which this calculation is needed would probably pertain to something more than just integers (e.g., the Dropbox candidate screening exercise). The words are there to stand in for whatever the integers might represent, and thereby to allow other programming language features than arithmetic to be demonstrated in the solutions. 2) Although this is an NP complete problem, an efficient implementation is possible in practice when the weights are restricted to a manageable range as stipulated (e.g., -1000 to 1000). One only needs a bit vector with an entry for each possible sum, and a linear time traversal of the word list. I wanted to make it clear that an alternative to the brute force solution exists and is appropriate. --Sluggo 01:05, 3 January 2012 (UTC)