416. Partition Equal Subset Sum

leetcode medium

#array#csharp#dynamic-programming#hash-table#leetcode#medium

Task

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

Пример:

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

Output: true

C# solution

matched/original

public class Solution {
    public bool CanPartition(int[] nums) {
        int sum = nums.Sum();
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        bool[] dp = new bool[target + 1];
        dp[0] = true;
        
        foreach (int num in nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool CanPartition(vector<int>& nums) {
        int sum = nums.Sum();
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        bool[] dp = new bool[target + 1];
        dp[0] = true;
        
        foreach (int num in nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
}

Java solution

matched/original

public class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
}

JavaScript solution

matched/original

function canPartition(nums) {
    const sum = nums.reduce((a, b) => a + b, 0)
    if (sum % 2 !== 0) return false
    const target = sum / 2
    const dp = Array(target + 1).fill(false)
    dp[0] = true
    
    for (const num of nums) {
        for (let j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num]
        }
    }
    
    return dp[target]
}

Python solution

matched/original

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    
    return dp[target]

Go solution

matched/original

package main

func canPartition(nums []int) bool {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if sum%2 != 0 {
        return false
    }
    target := sum / 2
    dp := make([]bool, target+1)
    dp[0] = true
    
    for _, num := range nums {
        for j := target; j >= num; j-- {
            dp[j] = dp[j] || dp[j-num]
        }
    }
    
    return dp[target]
}

Explanation

Algorithm

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

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

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

😎