Re: array of integers

Hi,

----- Original Message -----
From: "Willem" <willem@xxxxxxxx>
Newsgroups: comp.programming
Sent: Friday, April 29, 2005 1:31 AM
Subject: 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.
>

Thanks for the clarification Willem. The paraphrase of yours is better; "all
subsets of the array that sum to an element of the array"
I am convinced the problem is NP-complete.
And inclusion of negative values make the problem even harder to tackle with
if you were to think of efficient ways.

I think I should impose a restriction on input, namely, allowing only
positive integers.
I am guessing CBFalconer's code, with a little modification, could at least
give me an approximate result (if not exhaustive listing of all
combinations) for the positive integers.

The other way is of course trying all 2^n subsets starting from one element
subsets growing towards the n elements, maybe equipped with some early
detection of impossible subsets (assuming the set is sorted). Moreover using
hash-tables may also prove useful as Thad mentioned.

>
> 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: Subset Sum problem (w/ limited scope)
    ... The "Subset Sum" problem (stated various ways depending on what you ... a subset of those integers that sums up to zero. ... Are there going to be duplicate values in your original array? ...
    (comp.lang.fortran)
  • Re: How can I find the greatest possible sum within 12 months? A newbie...
    ... It may be because you have headers, and when I tied it first I omitted ... You may have omitted to enter it as an array formula (see notes on ... the starting sum is in A2 and the end sum is in A123. ... Excel will insert them for you. ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Explanation of SUMPRODUCT
    ... I don't even think you need to enter it as an array ... Yes, we know this, but in this case SUM is an array formula SUMPRODUCT ... > each element is the number of times the corresponding cell value appears ...
    (microsoft.public.excel.programming)
  • Re: Simple but confusing algorith question
    ... As you mention that this is an interview question ... ... through the array, then query against the structure somehow. ... structure and the cost of querying the data structure. ... array 1,2,3,4 sum = 5 ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Simple but confusing algorith question
    ... bool MyPairSum(int array, int sum) ... indices that equal the input sum parameter. ...
    (microsoft.public.dotnet.languages.csharp)