一. 题目

二. 思路

• 所有和sum为奇数，则不可能分割两个元素和相等的子集。

• 就变成是否存在和为sum/2的选法，即01背包问题。

三. 代码

class Solution
{
    static final int N = 2, M = (int) 1e4 + 10;
    boolean[][] f = new boolean[N][M];

    public boolean canPartition(int[] nums)
    {
        int sum = Arrays.stream(nums).sum();
        int n = nums.length, m = sum / 2;
        if (sum % 2 != 0) return false;
        for (int i = 0; i < N; ++i) Arrays.fill(f[i], false);

        f[0][nums[0]] = true;
        for (int i = 1; i < n; ++i)
            for (int j = 0; j <= m; ++j)
            {
                f[i & 1][j] = f[i - 1 & 1][j];
                if (j >= nums[i]) f[i & 1][j] |= f[i - 1 & 1][j - nums[i]];
            }
        return f[n - 1 & 1][m];
    }
}