Я очень плохо разбираюсь в математике и вычислениях сложности, поэтому я хотел бы попросить вас о помощи.
Мне нужно написать функцию, которая принимает массив целых чисел и другое целое число и возвращает истину, если любая комбинация целых чисел внутри массива (сумма) равна другому целому числу и ложь в противном случае.
Лучший результат, которого я смог достичь, это O(n!)
— Довольно новичок в исполнении …
Не могли бы вы помочь мне написать такую функцию более эффективным способом?
Или, по крайней мере, дать мне подсказку.
Я думаю, что вы могли бы сделать это таким образом
На самом деле это может дать вам грубую силу, это зависит от данных.
Пример (1,2,3,4,5,6,7,8,9,10) и целое число для проверки — 1000.
Но вы можете проверить это на первом этапе. (добавлено как шаг 0)
Но проверка того, что результат уже недоступен, в начале поиска отбрасывает множество вариантов.
Я уверен, что это не самый лучший вариант, но не очень сложный для реализации, и он, как правило, отлично помогает при расчете.
Надеюсь, это понятно.
Я бы сделал массив сумм всех элементов в массиве. Например:
$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;
...
Затем, когда у вас есть этот массив (разумеется, вы должны выполнить цикл for, чтобы получить его), тогда вы можете искать, находится ли interger в array_sum.