使用 oh-my-zsh

416、分割等和子集

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

注意:

• 每个数组中的元素不会超过 100
• 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

链接：https://leetcode-cn.com/problems/partition-equal-subset-sum

题解

排序，找累加中位数

1、排序+二分查找+数字交换——行不通，可能要交换多个数字

1 1 2 3 5
1 2 4 7 12

• 代码

// java
class Solution {
    public boolean canPatition(int[] nums) {
        // 排序
        Arrays.sort(nums);
        int[] accSum = new int[nums.length+1];
        // 计算累计和
        for (int i = 0;i < nums.length;i++){
            accSum[i+1] = accSum[i] + nums[i];
        }
        // 总和不为偶数，一定不行
        if ((accSum[nums.length]&1) == 1) {
            System.out.println("over0");
            return false;
        }
        System.out.println("accSum: "+accSum[nums.length]);
        
        // 二分查找 累计和的一半
        int key = accSum[nums.length]/2;
        System.out.println("key: "+key);
        int l=1,r = nums.length;
        int firstLarge = 0;
        while(l<=r) {
            int mid = (l+r)/2;
            // 找到累计和的一般，直接返回
            if (accSum[mid] == key) {
                System.out.println("over1");
                return true;
            }
            if (accSum[mid] > key){
                if (accSum[mid - 1] <= key) {
                    firstLarge = mid;
                    break;
                }
                r = mid - 1;
            }else {
                if (mid + 1 < accSum.length && accSum[mid + 1] >= key) {
                    firstLarge = mid + 1;
                    break;
                }
                l = mid + 1;
            }
        }
        // 找到累计和的一般，直接返回
        if (accSum[firstLarge] == key || accSum[firstLarge - 1] == key ) {
            System.out.println("over2");
            return true;
        }
        System.out.println("firstLarge: "+firstLarge);
        // 没找到，进行数组的元素交换，以达到目标值
        // 1换1
        int diff = accSum[nums.length] - 2*accSum[firstLarge-1];
        if ((diff & 1) == 0) {
            for (int i = firstLarge-2;i >= 0;i--) {
                int tmp = nums[firstLarge-1] - nums[i];
                if (tmp == diff/2) {
                    return true;
                }
            }
            // 没找到，进行数组的值交换，以达到目标值
            for (int i = firstLarge-1;i < nums.length;i++) {
                int tmp = nums[i] - nums[firstLarge-2];
                if (tmp == diff/2) {
                    return true;
                }
            }
        }
        // 不存在
        System.out.println("over5");
        return false;
    }

}

2、二维动态规划

$dp[i][j]$ 表示nums[0…i]是否可以划分为大小为j的两个子数组。

$dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]$

• 代码

// java
class Solution {
    public boolean canPatition(int[] nums) {
        // 获取数组的长度
        int len = nums.length;
        // 空数组判断
        if (len == 0) {
            return false;
        }
        // 求总和
        int sum = 0;
        for (int num : nums) {
            sum+=num;
        }

        // 总和为奇数，直接返回false
        if ((sum & 1) == 1) {
            return false;
        }

        // 获取目标值
        int target = sum/2;

        // 创建二维状态数组
        boolean[][] dp = new boolean[len][target+1];

        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }

        // 更新dp状态, i表示当前数组的最大下标
        for (int i = 1;i < len;i++) {
            //  更新每一个j是否有部分元素的和与之相等
            for (int j = 0;j <= target;j++) {
                dp[i][j] = dp[i-1][j];
                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                }
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i-1][j - nums[i]];
                }
            }
        }

        return dp[len - 1][target];
    }
}

// 优化一下
public class Solution {

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return false;
        }

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

        if ((sum & 1) == 1) {
            return false;
        }

        int target = sum / 2;

        boolean[][] dp = new boolean[len][target + 1];
        // 初始化成为 true 虽然不符合状态定义，但是从状态转移来说是完全可以的
        dp[0][0] = true;

        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j <= target; j++) {

                dp[i][j] = dp[i - 1][j];

                if (nums[i] <= j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }

            // 由于状态转移方程的特殊性，提前结束，可以认为是剪枝操作
            if (dp[i][target]) {
                return true;
            }
        }
        return dp[len - 1][target];
    }
}

// 作者：liweiwei1419
// 链接：https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/

3、动态规划空间压缩

由于第一维度的相邻状态更新，可以降低一个纬度。滚动更新数组。

• 代码

// java
public class Solution {

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return false;
        }

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

        if ((sum & 1) == 1) {
            return false;
        }

        int target = sum / 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        if (nums[0] <= target) {
            dp[nums[0]] = true;
        }

        for (int i = 1; i < len; i++) {
            for (int j = target; nums[i] <= j; j--) {
                if (dp[target]) {
                    return true;
                }

                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}

// 作者：liweiwei1419
// 链接：https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/

4、递归求和

自上而下递归，自下而上求解

// 递归更新目标值
class Solution {
    public boolean canPartition(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;
        sum/=2;
        return helper(nums,0,sum);
    }
    private boolean helper(int[] nums,int index,int target){
        if(target==0)
            return true;
        if(index==nums.length||target<0)
            return false;
        if(helper(nums,index+1,target-nums[index]))
            return true;
        //1 1 1 100
        //跳过相同的数
        int j=index+1;
        while(j<nums.length&&nums[index]==nums[j]){
            j++;
        }
        // 
        return helper(nums,j,target);
    }
}

// 二分递归，不断减少目标值

class Solution {
    public boolean canPartition(int[] nums) {

        // 1.涉及到剪枝,所以得做下对原始数组的排序
        Arrays.sort(nums);

        // 求出整个集合S的求和值Sum(S)
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

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

        // 先求出集合S求和值的一半[Sum(S)/2], 作为"accpet"和"pass"集合的上限;
        sum = sum/2;


        return canPartitionHelper(nums, nums.length - 1, sum, sum);
    }

    private boolean canPartitionHelper(int[] nums, int idx, int accept, int pass) {

        // 1.递归终止条件, 只要其中的一个集合累加值满足上限值, 即返回true
        if (accept == 0 || pass == 0) {
            return true;
        }

        // 2.剪枝
        if (accept < 0 || pass < 0) {
            return false;
        }

        // 3.分别将当前当前的值放入"accept"集合或者"pass"集合;
        return canPartitionHelper(nums, idx - 1, accept - nums[idx], pass)
                || canPartitionHelper(nums, idx - 1, accept, pass - nums[idx]);
    }
}

5、记忆化递归

class Solution {
    // dfs
    // 首先对数组求和，若和sum为奇数，显然不可能分割等和子集
    // 然后在数组中查看是否存在和为sum/2的子序列
    // 对每个元素a[i]，只有加入子序列和不加入两种情况
    // 加入则sum-a[i]，不加入则sum不变，i+1，继续求解两个子问题
    
    // 缓存子问题
    // dp[i][j]表示a[i,...]中是否存在和为j的子序列
    private Integer [][]dp;
    public boolean canPartition(int[] nums) {
        int sum=0;
        // 求和
        for(int n:nums) sum+=n;
        // 和为奇数，不可能等和分割
        if(sum%2!=0) return false;
        dp=new Integer[nums.length][sum/2+1];
        // 是否存在和为sum/2的子序列
        return dfs(sum/2,nums,0);
    }
    // [i,...]中是否存在和为sum的子序列
    private boolean dfs(int sum,int [] nums,int i){
        // 说明上一层已经找到解
        if(sum==0) return true;
        // 没有找到解
        if(sum<0 || i>=nums.length) return false;
        // 子问题已经有缓存
        if(dp[i][sum]!=null) return dp[i][sum] == 1;
        // 加入子序列和不加入子序列两种情况
        boolean res=dfs(sum-nums[i],nums,i+1)||dfs(sum,nums,i+1);
        // 缓存子问题
        dp[i][sum] = res?1:0;
        return res;
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com