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

示例 1：

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

示例 2：

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

解题思路

假设数组全部元素的和为 sum 。问题等价于：给一个数组 nums，是否可以从中找到若干数字，使得和为 sum/2 （target）

• 如果 sum 为奇数，那必定不可能，返回 false
• 如果数组中最大元素已经超过了sum/2 ，也必然不可能，也返回 false

剔除上述情况后，问题演变成：在一个数组中是否可以找到若干数字，使得和为 target （0-1背包问题）

动态规划

• 初始状态：初始化数组 dp[i][j]，表示从前 i 个元素中，是否可以选出若干个数，使其总和正好等于 j 。
  • 纵向（i变化）表示第几个数字（ i 从 0 开始一直到数组长度）
  • 横向（j变化）表示从凑成的和 （ j 从 0 开始一直到题目目标 target 为止 0 1 2 3 ... target）
  • 初始化时，为了保证逻辑一致，横向纵向都开 + 1

当我们选定题目数组中的某个数字 currNum = nums[i-1] 时，

• 如果 currNum > j，说明当前数字比目标和还要大，无法选择，所以 dp[i][j] = dp[i-1][j]
• 如果 currNum <= j，说明当前数字可以被选择，此时有两种情况：
  • 不选择 currNum：dp[i-1][j]
  • 选择 currNum：dp[i-1][j-currNum]
  • 所以 dp[i][j] = dp[i-1][j] || dp[i-1][j-currNum]

Java 实现

    public boolean canPartition(int[] nums) {
        if (nums.length < 2){
            return false;
        }
        int sum = 0;
        int maxNum = 0;
        for (int i = 0; i < nums.length; i++){
            sum += nums[i];
            maxNum = Math.max(maxNum, nums[i]);
        }
        // 如果和为奇数，不可能分割成两个和相同的子集
        if (sum % 2 == 1){
            return false;
        }
        // 问题转变为：数组nums中，是否存在若干元素的和为 target 
        int target = sum / 2;
        // 如果数组中最大元素已经超过了 target，必然不可能
        if (maxNum > target){
            return false;
        }
        // i 表示数组的前 i 个数， j 表示凑成某个和 （0 <= j <= target）
        boolean dp[][] = new boolean[nums.length+1][target+1];
        // 初始化首列，对于任意数字nums[i]，目标和为 0 都可通过【不选任何元素】来实现
        for (int i = 0; i < nums.length + 1; i++){
            dp[i][0] = true;
        }
        // 初始化首行，对于前0个元素，必然无法凑出任何和，返回false
        // 由于 boolean 默认就是 false，无需编码
        // 如果开的是 boolean[n][target + 1]; ，那就得考虑 dp[0][nums[0]] = true

        // 初始化其他元素
        for (int i = 1; i < nums.length + 1; i++){
            int currNum = nums[i-1];
            for (int j = 1; j <= target; j++){
                if (currNum > j){
                    // 数字太大，无法选
                    dp[i][j] = dp[i-1][j];
                } else {
                    // 选 or 不选
                    // 不选：前 i-1 个元素能否凑成和
                    // 选：  前 i-1 个元素能否凑成剩余的和
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-currNum];
                }
            }
            // 如果没有全部遍历完已经找到满足的，提前返回
            if (dp[i][target] == true) return true;
        }
        return dp[nums.length][target];
    }