Re: array of integers
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.
In general, trying out techniques with pencil and paper is how I often
develop algorithms for a new problem. I try to think of some systematic
way to approach it.
My first thought would be to sort the array.
In your case, since there are no restrictions on the number of elements
in the array or their values, you need to consider the special case of
duplicate entries. For multiple entries, simply choose the number of
copies of the duplicated element to include in the trial set. For
testing sums, you might use a bit array, hash table, or binary search.
If your entries were all positive, you could do a much quicker search
than what is required for mixed sign entries.
Thad
.
Relevant Pages
- Re: Constant time insertion into a sorted list?
... I tried a straight-forward priority queue implemented with an array. ... As soon as you allocate an array, the maximum number of entries is ... fixed by the size of the array, hence regardless of what algorithm ... To make insertion constant with the method you ...
(comp.programming) - Re: Binary Search
... To make the algorithm simpler. ... It's a compromise between datastructure ... Use an array without duplicates, where an element contains not only ... pseudocode for a two-stage binary search. ...
(comp.lang.pascal.delphi.misc) - Re: Constant time insertion into a sorted list?
... I tried a straight-forward priority queue implemented with an array. ... As soon as you allocate an array, the maximum number of entries is ... fixed by the size of the array, hence regardless of what algorithm ... Dequeue the most urgent entry and set it aside, enqueue a dummy, return saved value. ...
(comp.programming) - Re: search operation
... This algorithm requires Ocomparisons. ... a person who knows that binary search is generally more efficient than a linear one might immediately come up with an obvious idea: what if in the above algorithm we use binary search instead of the linear one. ... This means that when the values of M and N are pretty close to each other, the linear search based algorithm will win considerably over the binary search based algorithm. ... In this case linear search begins from the first element of array B, stops at some location, then continues from the previous location and so on until the end of array B is finally reached. ...
(comp.programming) - Re: Compare Text Files
... If you're using binary search you want to make sure the arrays are ... array you'll have to implement a sort routine on the array to search ... Let's say you want to search File1 for the entries in File2. ... A sample script might look like this: ...
(microsoft.public.scripting.vbscript) |
|
