Алгоритми та структури даних · Middle · Запитання 75 з 75
Subset sum: чи можуть деякі з чисел дати в сумі target? Яке класичне рішення через DP?
- 1Відсортувати числа й жадібно брати найбільші, що ще вміщуються
- 2Перебрати всі перестановки чисел і перевірити їхні суми
- ✓Правильна відповідь: Булева таблиця досяжних сум, що оновлюється для кожного числа: O(n × target)
Пояснення
reachable[s] каже, чи можна скласти суму s; для кожного числа оновлюємо суми від більших до менших, щоб воно використовувалося один раз. Жадібний підхід може пропустити рішення, а перестановки - O(n!). DP псевдополіноміальне: швидке, лише поки target малий.