Skip to content

Latest commit

 

History

History
580 lines (473 loc) · 18.7 KB

0416.分割等和子集.md

File metadata and controls

580 lines (473 loc) · 18.7 KB
Raw

参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

416. 分割等和子集

力扣题目链接

题目难易：中等

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

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

示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

思路

这道题目初步看，是如下两题几乎是一样的，大家可以用回溯法，解决如下两题

  • 698.划分为k个相等的子集
  • 473.火柴拼正方形

这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。

本题是可以用回溯暴力搜索出所有答案的，但最后超时了，也不想再优化了，放弃回溯，直接上01背包吧。

如果对01背包不够了解，建议仔细看完如下两篇：

01背包问题

背包问题，大家都知道，有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

背包问题有多种背包方式，常见的有：01背包、完全背包、多重背包、分组背包和混合背包等等。

要注意题目描述中商品是不是可以重复放入。

即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的。

要明确本题中我们要使用的是01背包，因为元素我们只能用一次。

回归主题：首先，本题要求集合里能否出现总和为 sum / 2 的子集。

那么来一一对应一下本题，看看背包问题如果来解决。

只有确定了如下四点，才能把01背包问题套到本题上来。

  • 背包的体积为sum / 2
  • 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
  • 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。

以上分析完，我们就可以套用01背包，来解决这个问题了。

动规五部曲分析如下：

  1. 确定dp数组以及下标的含义

01背包中，dp[j] 表示： 容量为j的背包，所背的物品价值可以最大为dp[j]。

套到本题，dp[j]表示 背包总容量是j，最大可以凑成j的子集总和为dp[j]。

  1. 确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

  1. dp数组如何初始化

在01背包，一维dp如何初始化，已经讲过，

从dp[j]的定义来看，首先dp[0]一定是0。

如果如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。

本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。

代码如下：

// 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
// 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
vector<int> dp(10001, 0);
  1. 确定遍历顺序

在动态规划：关于01背包问题，你该了解这些！（滚动数组）中就已经说明：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

代码如下：

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
  1. 举例推导dp数组

dp[j]的数值一定是小于等于j的。

如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j，理解这一点很重要。

用例1，输入[1,5,11,5] 为例，如图：

416.分割等和子集2

最后dp[11] == 11，说明可以将这个数组分割成两个子集，使得两个子集的元素和相等。

综上分析完毕，C++代码如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;

        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 2 == 1) return false;
        int target = sum / 2;

        // 开始 01背包
        for(int i = 0; i < nums.size(); i++) {
            for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        // 集合中的元素正好可以凑成总和target
        if (dp[target] == target) return true;
        return false;
    }
};
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n)，虽然dp数组大小为一个常数，但是大常数

总结

这道题目就是一道01背包应用类的题目，需要我们拆解题目，然后套入01背包的场景。

01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2。

看代码的话，就可以发现，基本就是按照01背包的写法来的。

其他语言版本

Java：

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int n = nums.length;
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        //总和为奇数，不能平分
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for(int i = 0; i < n; i++){
            for(int j = target; j >= nums[i]; j--){
                //物品 i 的重量是 nums[i]，其价值也是 nums[i]
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }
}
public class Solution {
    public static void main(String[] args) {
        int num[] = {1,5,11,5};
        canPartition(num);

    }
    public static boolean canPartition(int[] nums) {
        int len = nums.length;
        // 题目已经说非空数组，可以不做非空判断
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 特判：如果是奇数，就不符合要求
        if ((sum %2 ) != 0) {
            return false;
        }

        int target = sum / 2; //目标背包容量
        // 创建二维状态数组，行：物品索引，列：容量（包括 0）
        /*
        dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数
          每个数只能用一次，使得这些数的和恰好等于 j。
        */
        boolean[][] dp = new boolean[len][target + 1];

        // 先填表格第 0 行，第 1 个数只能让容积为它自己的背包恰好装满  （这里的dp[][]数组的含义就是“恰好”，所以就算容积比它大的也不要）
        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];

                //如果某个物品单独的重量恰好就等于背包的重量，那么也是满足dp数组的定义的
                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                }
                //如果某个物品的重量小于j，那就可以看该物品是否放入背包
                //dp[i - 1][j]表示该物品不放入背包，如果在 [0, i - 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
                //dp[i - 1][j - nums[i]]表示该物品放入背包。如果在 [0, i - 1] 这个子区间内就得找到一部分元素，使得它们的和为 j - nums[i]。
                if (nums[i] < j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= target; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        return dp[len - 1][target];
    }
}
//dp数组的打印结果
false true false false false false false false false false false false 
false true false false false true true false false false false false 
false true false false false true true false false false false true 
false true false false false true true false false false true true

二维数组版本（易于理解）：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        if (sum % 2 == 1)
            return false;
        int target = sum / 2;

        //dp[i][j]代表可装物品为0-i，背包容量为j的情况下，背包内容量的最大价值
        int[][] dp = new int[nums.length][target + 1];

        //初始化,dp[0][j]的最大价值nums[0](if j > weight[i])
        //dp[i][0]均为0，不用初始化
        for (int j = nums[0]; j <= target; j++) {
            dp[0][j] = nums[0];
        }

        //遍历物品，遍历背包
        //递推公式:
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                //背包容量可以容纳nums[i]
                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][target] == target;
    }
}

Python：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        target = sum(nums)
        if target % 2 == 1: return False
        target //= 2
        dp = [0] * 10001
        for i in range(len(nums)):
            for j in range(target, nums[i] - 1, -1):
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
        return target == dp[target]

Go：

// 分割等和子集 动态规划
// 时间复杂度O(n^2) 空间复杂度O(n)
func canPartition(nums []int) bool {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    // 如果 nums 的总和为奇数则不可能平分成两个子集
    if sum % 2 == 1 {
        return false
    }
    
    target := sum / 2
    dp := make([]int, target + 1)

    for _, num := range nums {
        for j := target; j >= num; j-- {
            if dp[j] < dp[j - num] + num {
                dp[j] = dp[j - num] + num
            }
        }
    }
    return dp[target] == target
}
func canPartition(nums []int) bool {
    /**
    动态五部曲：
        1.确定dp数组和下标含义
        2.确定递推公式
        3.dp数组初始化
        4.dp遍历顺序
        5.打印
    **/
    //确定和
    var sum int
    for _,v:=range nums{
        sum+=v
    }
    if sum%2!=0{   //如果和为奇数，则不可能分成两个相等的数组
        return false
    }
    sum/=2
    //确定dp数组和下标含义
    var dp [][]bool //dp[i][j] 表示： 前i个石头是否总和不大于J
    //初始化数组
    dp=make([][]bool,len(nums)+1)
    for i,_:=range dp{
        dp[i]=make([]bool,sum+1)
        dp[i][0]=true
    }
    for i:=1;i<=len(nums);i++{
        for j:=1;j<=sum;j++{//j是固定总量
            if j>=nums[i-1]{//如果容量够用则可放入背包
                dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]]
            }else{//如果容量不够用则不拿，维持前一个状态
                dp[i][j]=dp[i-1][j]
            }
        }
    }
    return dp[len(nums)][sum]
}

javaScript:

var canPartition = function(nums) {
    const sum = (nums.reduce((p, v) => p + v));
    if (sum & 1) return false;
    const dp = Array(sum / 2 + 1).fill(0);
    for(let i = 0; i < nums.length; i++) {
        for(let j = sum / 2; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            if (dp[j] === sum / 2) {
                return true;
            }
        }
    }
    return dp[sum / 2] === sum / 2;
};

C: 二维dp：

/**
1. dp数组含义：dp[i][j]为背包重量为j时，从[0-i]元素和最大值
2. 递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
3. 初始化：dp[i][0]初始化为0。因为背包重量为0时，不可能放入元素。dp[0][j] = nums[0]，当j >= nums[0] && j < target时
4. 遍历顺序：先遍历物品，再遍历背包
*/
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int getSum(int* nums, int numsSize) {
    int sum = 0;

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

bool canPartition(int* nums, int numsSize){
    // 求出元素总和
    int sum = getSum(nums, numsSize);
    // 若元素总和为奇数，则不可能得到两个和相等的子数组
    if(sum % 2)
        return false;

    // 若子数组的和等于target，则nums可以被分割
    int target = sum / 2;
    // 初始化dp数组
    int dp[numsSize][target + 1];
    // dp[j][0]都应被设置为0。因为当背包重量为0时，不可放入元素
    memset(dp, 0, sizeof(int) * numsSize * (target + 1));

    int i, j;
    // 当背包重量j大于nums[0]时，可以在dp[0][j]中放入元素nums[0]
    for(j = nums[0]; j <= target; ++j) {
        dp[0][j] = nums[0];
    }

    for(i = 1; i < numsSize; ++i) {
        for(j = 1; j <= target; ++j) {
            // 若当前背包重量j小于nums[i]，则其值等于只考虑0到i-1物品时的值
            if(j < nums[i])
                dp[i][j] = dp[i - 1][j];
            // 否则，背包重量等于在背包中放入num[i]/不放入nums[i]的较大值
            else
                dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j  - nums[i]] + nums[i]);
        }
    }
    // 判断背包重量为target，且考虑到所有物品时，放入的元素和是否等于target
    return dp[numsSize - 1][target] == target;
}

滚动数组：

/**
1. dp数组含义：dp[j]为背包重量为j时，其中可放入元素的最大值
2. 递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
3. 初始化：均初始化为0即可
4. 遍历顺序：先遍历物品，再后序遍历背包
*/
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int getSum(int* nums, int numsSize) {
    int sum = 0;

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

bool canPartition(int* nums, int numsSize){
    // 求出元素总和
    int sum = getSum(nums, numsSize);
    // 若元素总和为奇数，则不可能得到两个和相等的子数组
    if(sum % 2)
        return false;
    // 背包容量
    int target = sum / 2;

    // 初始化dp数组，元素均为0
    int dp[target + 1];
    memset(dp, 0, sizeof(int) * (target + 1));

    int i, j;
    // 先遍历物品，后遍历背包
    for(i = 0; i < numsSize; ++i) {
        for(j = target; j >= nums[i]; --j) {
            dp[j] = MAX(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    
    // 查看背包容量为target时，元素总和是否等于target
    return dp[target] == target;
}

TypeScript:

一维数组，简洁

function canPartition(nums: number[]): boolean {
    const sum: number = nums.reduce((pre, cur) => pre + cur);
    if (sum % 2 === 1) return false;
    const bagSize: number = sum / 2;
    const goodsNum: number = nums.length;
    const dp: number[] = new Array(bagSize + 1).fill(0);
    for (let i = 0; i < goodsNum; i++) {
        for (let j = bagSize; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        }
    }
    return dp[bagSize] === bagSize;
};

二维数组，易懂

function canPartition(nums: number[]): boolean {
    /**
        weightArr = nums;
        valueArr = nums;
        bagSize = sum / 2; (sum为nums各元素总和);
        按照0-1背包处理
     */
    const sum: number = nums.reduce((pre, cur) => pre + cur);
    if (sum % 2 === 1) return false;
    const bagSize: number = sum / 2;
    const weightArr: number[] = nums;
    const valueArr: number[] = nums;
    const goodsNum: number = weightArr.length;
    const dp: number[][] = new Array(goodsNum)
    	.fill(0)
    	.map(_ => new Array(bagSize + 1).fill(0));
    for (let i = weightArr[0]; i <= bagSize; i++) {
        dp[0][i] = valueArr[0];
    }
    for (let i = 1; i < goodsNum; i++) {
        for (let j = 0; j <= bagSize; j++) {
            if (j < weightArr[i]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weightArr[i]] + valueArr[i]);
            }
        }
    }
    return dp[goodsNum - 1][bagSize] === bagSize;
};