Re: array of integers

Arthur wrote:
)
) 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".)

That's almost what he wants, just that he wants it not for a single number,
but for a set of numbers (namely, the array).

I thought he'd made that clear enough: he wants all subsets of the array
that sum to an element of the array.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
.

Relevant Pages

  • Re: array of integers
    ... with an algorithm to find all combinations of elements that add up to the ... to 8?", then that's a variant of the subset-sum problem, which is hard. ... If, as I suspect, you just want a new array consisting of all the ... If you can find out some interesting properties of the input array and target, ...
    (comp.programming)
  • Re: simple increment operator question.
    ... Arthur J. O'Dwyer wrote... ... value between 0 and one less than the size of the array. ... type to use for such is size_t, since you can't rely on an int being big ... *+) when adding integral values and pointers. ...
    (alt.comp.lang.learn.c-cpp)