Re: array of integers
- From: "Arthur J. O'Dwyer" <ajo@xxxxxxxxxxxxxxxxxxxxx>
- Date: Fri, 29 Apr 2005 00:54:30 -0400 (EDT)
On Thu, 28 Apr 2005, Kemal Oral CANSIZLAR wrote:
There is an array of integers, without any restriction. How can I come up with an algorithm to find all combinations of elements that add up to the numbers in the array. If array is {1, 3, 2, 5, 4}, result would be {1, 2} = 3 is in array; {1, 3} = 4 is in array; {2, 3} = 5 is in array; {1, 4} = 5 is in array.
That depends in what format your input and output need to be. I think (but I'm no expert) that if you're given a set (say {1,3,6,7}) and some value (say 8) by the user, and asked "does any subset of {1,3,6,7} sum to 8?", then that's a variant of the subset-sum problem, which is hard. (For the definition of "hard" in this context, Google "NP-complete".)
If, as I suspect, you just want a new array consisting of all the subset-sums of the input array --- {0,1,3,4,6,7,8,9,10,11,13,14,16,17}
--- then that seems like an easier problem. (I mean, you can do all the
work once and then just do a search of the output array to determine
whether any input number is in it or not.) You can do that in O(2^n)
time by just generating all the combinations of the input array's elements.
Sure, it's slow for big inputs, but I don't think you can do any better
/without any restrictions/, as you said. If you can find out some interesting properties of the input array and target, then maybe you can
solve some special cases. (E.g., if the target is less than the minimum
element of the array; if the target is odd and all the array elements are
even; that sort of thing.)
Maybe someone here knows the state of the art in heuristics for this kind of problem; I don't.
HTH, -Arthur .
- Follow-Ups:
- Re: array of integers
- From: Willem
- Re: array of integers
- References:
- array of integers
- From: Kemal Oral CANSIZLAR
- array of integers
- Prev by Date: Re: auto-extracting for dll
- Next by Date: Re: Simulate user interaction - Avoid screen saver activation
- Previous by thread: Re: array of integers
- Next by thread: Re: array of integers
- Index(es):
Relevant Pages
|
