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
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 = $int1 + $int2; $array_sum = $int1 + $int3; $array_sum = $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.