问题描述:

I am really bad in math and complexity calculations so I would like to ask you for help.

I need to write a function which takes an array of integers and another integer and returns true if any combination of integers inside the array (sum) equals to the another integer and false otherwise.

The best result I was able to achieve is O(n!) - Pretty newbie performance...

Could you please help me write such a function in a more efficient way?

Or at least give me a hint.

网友答案:

I think you could do it in that way

  1. if(sum(intgers)) < another integer return false
  2. Take first integer
  3. current = first
  4. foreach (number in left integers)
  5. result = current + number
  6. if result = another integer return true
  7. if result > another integer end this tree
  8. else current = result
  9. to step 3 with new data. And so on with recursion.

In fact it can give you bruteforce, it have dependency on data. Example (1,2,3,4,5,6,7,8,9,10) and integer to check is 1000. But you can check it in the first step. (added as step 0)

But checking that result is already not available will drop a lot of variants in the beginning of search.

I am sure it s not best, but not very hard to implement and it usually helps great with calculation. Hope it is understandable.

网友答案:

I would make an array of sums of all elements in array. For example:

$array_sum[0] = $int1 + $int2;
$array_sum[1] = $int1 + $int3;
$array_sum[2] = $int1 + $int4;
...
$array_sum[n] = $int1 + $intn;
$array_sum[n+1] = $int2 + $int1;
$array_sum[n+2] = $int2 + $int3;
$array_sum[n+3] = $int2 + $int4;
...

Then, when you have that array (of course, you must do a for loop to get it) then you can search if the interger is in the array_sum.

相关阅读:
Top