题解 | #分割等和子集#

import java.util.*;


public class Solution {
    
    public int num = 0; // 定义一个整型变量，用于存放数组中全部数字相加的结果

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param nums int整型一维数组
     * @return bool布尔型
     */
    public boolean partition(int[] nums) {
        // write code here
        // 一些特殊情况的处理
        if (1 == nums.length) {
            return false;
        }
        // 求出 num
        for (int i = 0; i < nums.length; i++) {
            num += nums[i];
        }
        // 如果数组中的数字全部相加的结果为奇数，那么一定是 false(根本无法均分成两份)
        if (num % 2 != 0) {
            return false;
        }
        // 记忆化搜索
        int[][] dp = new int[nums.length + 1][num + 1];
        for (int i = 0; i < nums.length + 1; i++) {
            for (int j = 0; j < num + 1; j++) {
                dp[i][j] = Integer.MIN_VALUE;
            }
        }
        return process(nums, 0, 0, dp) == 1 ? true : false;
    }

    public int process(int[] nums, int index, int currentNum, int[][] dp) {
        if (dp[index][currentNum] == Integer.MIN_VALUE) {
            if (currentNum * 2 == num) {
                dp[index][currentNum] = 1;
            } else if (index >= nums.length) {
                dp[index][currentNum] = 0;
            } else {
                dp[index][currentNum] = Math.max(process(nums, index + 1, currentNum, dp), process(nums, index + 1, currentNum + nums[index], dp));
            }
        }
        return dp[index][currentNum];
    }
}