1.题目

给你一个 只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum

2.思路

（1）动态规划
思路参考经典动态规划：0-1 背包问题的变体。

3.代码实现（Java）

//思路1————动态规划
public boolean canPartition(int[] nums) {
    int length = nums.length;
    //sum为数组所有元素之和
    int sum = 0;
    for (int i = 0; i < length; i++) {
        sum += nums[i];
    }
    //当和为奇数时，不可能将这个数组分割成两个和相等的子集
    if (sum % 2 != 0) {
        return false;
    }
    /*
        将问题转化为背包问题：
        给一个可装载重量为 sum/2 的背包和 N 个物品，每个物品的重量为 nums[i]，
        现在让你装物品，是否存在一种装法，能够恰好将背包装满？       
    */
    sum /= 2;
    /*
        dp[i][j] = flag
        对于前 i 个物品，当前背包的容量为 j 时，
        若 flag 为 true，则说明可以恰好将背包装满，若 x 为 false，否则说明不能恰好将背包装满
    */
    boolean[][] dp = new boolean[length + 1][sum + 1];
    //初始化基本情况
    for (int i = 0; i <= length; i++) {
        dp[i][0] = true;;
    }
    for (int i = 1; i <= length; i++) {
        for (int j = 1; j <= sum; j++) {
            if (j < nums[i - 1]) {
                //背包容量不足，不能装入第 i 个物品
                dp[i][j] = dp[i - 1][j];
            } else {
                /*
                    背包容量足够，此时对于第 i 个物品，有以下两种选择：
                    (1) 装入：那么是否能够恰好装满背包，取决于状态 dp[i - 1][j-nums[i - 1]]
                    (2) 不装入：那么是否能够恰好装满背包，取决于上一个状态 dp[i - 1][j]，继承之前的结果
                */
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }
    return dp[length][sum];
}