分割等和子集

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    public boolean partition (int[] nums) {
        // write code here
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(sum % 2 != 0){
            return false;
        }
        int n = sum / 2;
        int[][] dp = new int[nums.length][n + 1];
        for(int i = 1; i < nums.length; i++){
            for(int j = 1; j <= n; j++){
                // 可以放
                if(j >= nums[i]){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                }else{
                     dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length - 1][n] == n;
    }
}

1. 当rest<0时，表示本次凑数方案失败；
2. 当rest=0时，刚好凑齐，本次凑数方案是成功的；
3. 否则看本轮取哪个数nums[i]，下一轮需要凑rest-nums[i]。

private boolean recurrent(int[] nums, int depth, int rest) {
    if(rest < 0) return false;
    if(rest == 0) return true;    // base case
    for(int i = depth; i < nums.length; i++){
        if(recurrent(nums, i, rest - nums[i])) return true;
    }
    return false;
}

动态规划 

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return bool布尔型
     */
    public boolean partition (int[] nums) {
        // write code here
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        // 无法均分
        if(sum % 2 != 0){
            return false;
        }
        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length][target + 1];
        for(int i = 0; i < nums.length; i++){
            dp[i][0] = true;    // base case
        }
        for(int i = 0; i < nums.length; i++){
            for(int rest = nums[i]; rest <= target; rest++){
                dp[i][rest] |= dp[i][rest - nums[i]];
            }
        }
        return dp[0][target];
    }
}