剑指offer101：分割等和子集

题目：

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

示例一：

输入：nums = [1,5,11,5]

输出：true

解释：nums 可以分割成 [1, 5, 5] 和 [11] 。

示例二：

输入：nums = [1,2,3,5]

输出：false

解释：nums 不可以分为和相等的两部分

分析：

状态转移方程：

函数f(i,j)表示能否从前i个物品（标号为0,1,…,i-1）,中选择若干物品放满容量为j的背包，如果共有n个物品，背包容量为t，那么f(n,t)就是问题的解。

当判断能否从前i个物品中选择若干物品放满容量为j的背包时，对标号为i-1的物品有两个选择。一个选择是将标号为i-1的物品放入背包中，如果能从前i-1个物品中选择若干物品放满容量为j-nums[i-1]的背包，那么f（i,j）为true，另外一个选择是不将标号为i-1的物品放入背包中，如果i-1个物品中选择若干物品放满容量为j的背包，那么f(i,j)也为true。

• 当j等于0时，即背包得容量为0，不论有多少个物品，只要什么物品都不选择，就能使选中的物品的总重量为0，因此f(i,0)都为true。
• 当i等于0时，即物品的数量为0，肯定无法用0个物品来放满容量大于0的背包，因此j大于0时，f(0,j)都为false。
  
  例：
  判断f(2,4)时，先选择不将当前下标的值也就是4放入包中，发现前一个值也就是3不满足背包容量4的要求也就是f（2，4）=false,所以换另一个选择就是把当前下标的值也就是4算在内，满不满足容量4，f(2,4)=dp[2-1][4-4]=f(1,0)=true,所以满足需求.
  具体细节见代码

代码：

public class CanPartition {
    public static void main(String[] args) {
        CanPartition canPartition = new CanPartition();
        int[] nums = {3, 4, 1};
        boolean b = canPartition.canPartition(nums);
        System.out.println(b);
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        }
        return subsetSum(nums, sum / 2);
    }

    private boolean subsetSum(int[] nums, int target) {
//        创建一个二维数组
        boolean[][] dp = new boolean[nums.length + 1][target + 1];
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j <= target; j++) {
//                选择不将当前标号的物品放入包中
                dp[i][j] = dp[i - 1][j];
//                选择将当前标号的物品放入包中
                if (!dp[i][j] && j >= nums[i - 1]) {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]];
                }
            }

        }
        return dp[nums.length][target];
    }

    //    优化空间效率
    private boolean subsetSum2(int[] nums, int target) {
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 1; i < nums.length; i++) {
            for (int j = target; j > 0; j--) {
//                如果dp[j] = true就保留
                if (!dp[j] && j >= nums[i - 1]) {
                    dp[j] = dp[j - nums[i - 1]];
                }
            }
        }
        return dp[target];
    }
}