1、前言

2、思路

采用 0-1 背包思路，能不能分为两个相等的子集相当于从数组中找出：前 n 个数的和 = sum / 2（sum 为数组总和）。
定义函数 dp[i][j] = x，表示：
对于前 i 个物品，当前背包容量为 j 时，若 x 为 true，则说明恰好将背包装满；若 x 为 false，则说明不能将背包装满。

对于动态规划的代码来说，如果不会压缩成一维的，那么直接按照二维的做，除了浪费一点空间没其他的坏处。压缩成一维过后，内层循环要开始倒序，要不然同一层循环中，dp[j] 的值会被赋予成新值。

3、代码

记忆化递归：

public boolean canPartition2(int[] nums) {
        if(nums == null || nums.length == 0){
            return false;
        }

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if(sum % 2 != 0){
            return false;
        }

        Boolean[][] memo = new Boolean[nums.length][sum / 2 + 1];

        return dfs(nums, 0, sum / 2, memo);

    }

    private boolean dfs(int[] nums, int index, int target, Boolean[][] memo) {
        if(index >= nums.length){
            return false;
        }

        if(target == 0){
            return true;
        }

        if(memo[index][target] != null){
            return memo[index][target];
        }

        for (int i = index; i < nums.length; i++) {
            if(nums[i] > target){
                continue;
            }

            boolean res = dfs(nums, i + 1, target - nums[i], memo);
            memo[index][target] = res;
            if(res){
                return res;
            }
        }

        return false;
    }

动态规划：

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0){
            return false;
        }

        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }

        if(sum % 2 != 0){
            return false;
        }

        sum = sum / 2;
        int m = nums.length;
        boolean[][] dp = new boolean[m + 1][sum + 1];
        for(int i = 0; i <= m; i++){
            dp[i][0] = true;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= sum; j++){
                if(j < nums[i - 1]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j];
                }
            }
        }

        return dp[m][sum];
    }
}