416. Partition Equal Subset Sum

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];
    }
}

#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];
    }
}

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];
    }
}

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]
}

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]

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]
}

Algorithm

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

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

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

😎