Задача: 416. Partition Equal Subset Sum
Сложность: medium

Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.

Пример:

Input: nums = [1,5,11,5]
Output: true

👨‍💻 Алгоритм:

1⃣Проверьте, является ли сумма всех элементов массива четной. Если нет, верните false.

2⃣Используйте динамическое программирование для определения, можно ли найти подмножество с суммой, равной половине от общей суммы элементов.

3⃣Инициализируйте массив для хранения возможных сумм и обновляйте его, проверяя каждое число в массиве.

😎 Решение:

function canPartition($nums) {
    $sum = array_sum($nums);
    if ($sum % 2 != 0) return false;
    $target = $sum / 2;
    $dp = array_fill(0, $target + 1, false);
    $dp[0] = true;
    
    foreach ($nums as $num) {
        for ($j = $target; $j >= $num; $j--) {
            $dp[$j] = $dp[$j] || $dp[$j - $num];
        }
    }
    
    return $dp[$target];
}

Ставь 👍 и забирай 📚 Базу знаний