复杂性/ PHP - 数组内任何整数组合等于另一个整数

Question

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.

Answer 1

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.