Сложность / любая комбинация целых чисел внутри массива равна другому целому числу

Я очень плохо разбираюсь в математике и вычислениях сложности, поэтому я хотел бы попросить вас о помощи.

Мне нужно написать функцию, которая принимает массив целых чисел и другое целое число и возвращает истину, если любая комбинация целых чисел внутри массива (сумма) равна другому целому числу и ложь в противном случае.

Лучший результат, которого я смог достичь, это O(n!) — Довольно новичок в исполнении …

Не могли бы вы помочь мне написать такую ​​функцию более эффективным способом?
Или, по крайней мере, дать мне подсказку.

1

Решение

Я думаю, что вы могли бы сделать это таким образом

  1. если (сумма (intgers)) < другое целое число возвращает false
  2. Возьмите первое целое число
  3. текущий = первый
  4. foreach (число в целых числах слева)
  5. результат = текущий + номер
  6. если результат = другое целое число, вернуть true
  7. если результат> другое целое число, конец этого дерева
  8. иначе текущий = результат
  9. к шагу 3 с новыми данными. И так далее с рекурсией.

На самом деле это может дать вам грубую силу, это зависит от данных.
Пример (1,2,3,4,5,6,7,8,9,10) и целое число для проверки — 1000.
Но вы можете проверить это на первом этапе. (добавлено как шаг 0)

Но проверка того, что результат уже недоступен, в начале поиска отбрасывает множество вариантов.

Я уверен, что это не самый лучший вариант, но не очень сложный для реализации, и он, как правило, отлично помогает при расчете.
Надеюсь, это понятно.

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.

-1

По вопросам рекламы [email protected]