LeetCode-416. 分割等和子集

比眉伴天荒 2024-03-26 20:18 66阅读 0赞

#### 目录 ####

*   *  题目分析
     *  回溯法
     *  动态规划
     *  动态规划(压缩)

题目来源  
[416. 分割等和子集][416.]

### 题目分析 ###

这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。  
那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。

### 回溯法 ###

这道题和39. 组合总和非常类似(可以去做一下)  
[LeetCode-39. 组合总和][LeetCode-39.]

class Solution {
        
        boolean res;
        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;
            }
            //查找目标target的子集和
            int target = sum / 2;
            backTracking(nums,0,0,target);
            return res;
        }
    
        //startIndex为了数组不选取重复元素，sum为加起来的总和，target目标数
        private void backTracking(int[] nums,int startIndex,int sum,int target){
        
            //如果sum>target就没必要进行计算了
            if(sum > target){
        
                return;
            }
            //如果等于，直接将res设置为为true，相当于是相同子集了
            if(sum == target){
        
                res = true;
                return;
            }
            for(int i = startIndex;i<nums.length;i++){
        
                sum+=nums[i];
                backTracking(nums,i+1,sum,target);
                sum-=nums[i];  //回溯
            }
        }
    }

**这道题使用回溯算法不行(超时)，那么就要用动态规划了**  
![在这里插入图片描述][4e6b1f0ec5e446a0a3feaf637f3846af.png]

### 动态规划 ###

**背包问题**，大家都知道，有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。  
背包问题有多种背包方式，常见的有：**01背包、完全背包、多重背包、分组背包和混合背包等等。**  
要注意题目描述中商品是不是可以重复放入。  
即一个商品如果可以**重复多次放入是完全背包，而只能放入一次是01背包**，写法还是不一样的。  
**要明确本题中我们要使用的是01背包，因为元素我们只能用一次。**  
回归主题：首先，本题要求集合里能否出现总和为 sum / 2 的子集。  
那么来一一对应一下本题，看看背包问题如何来解决。  
只有确定了如下四点，才能把01背包问题套到本题上来。

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

理解了0-1背包问题，直接搬照着公式就可以写出  
[https://donglin.blog.csdn.net/article/details/129412502][https_donglin.blog.csdn.net_article_details_129412502]

class Solution {
        
        public boolean canPartition(int[] nums) {
        
            if(nums == null){
        
                return false;
            }
            int sum = 0;
            for(int num : nums){
        
                sum += num;
            }
            if(sum % 2 == 1){
        
                return false;
            }
            int target = sum / 2;
            int[][] dp = new int[nums.length][target+1];
            for(int j=target;j>=nums[0];j--){
        
                dp[0][j] = nums[0];
            }
            for(int i = 1;i<nums.length;i++){
        
                for(int j = 1;j<=target;j++){
        
                    if(j<nums[i]){
        
                        dp[i][j] = dp[i-1][j];
                    }else{
        
                        dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
                    }
                }
            }
            return dp[nums.length-1][target]==target;
        }
    }

![在这里插入图片描述][f0acb01492e24f8893341fb318266f6f.png]

### 动态规划(压缩) ###

**动规五部曲分析如下：**

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

01背包中，dp\[j\] 表示： 容量为j的背包，所背的物品价值最大可以为dp\[j\]。  
本题中每一个元素的数值既是重量，也是价值。  
套到本题，dp\[j\]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp\[j\]。  
那么如果背包容量为target， dp\[target\]就是装满 背包之后的重量，所以 当 dp\[target\] == target 的时候，背包就装满了。

*  2.确定递推公式

如果不清楚0-1背包问题的一维数组，可以看这篇  
[https://donglin.blog.csdn.net/article/details/129437136][https_donglin.blog.csdn.net_article_details_129437136]  
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\]);

*  3.dp数组如何初始化

在01背包，一维dp如何初始化，已经讲过，  
从dp\[j\]的定义来看，首先dp\[0\]一定是0。

*  4.确定遍历顺序

如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

for(int i = 0;i<nums.length;i++){
        
                for(int j = target;j>=nums[i];j--){
        
                    dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
                }
            }

*  5.举例推导dp数组

![在这里插入图片描述][31f75fbef4aa4af695a4f664a76e4214.png]

完整代码

class Solution {
        
        public boolean canPartition(int[] nums) {
        
            if(nums == null){
        
                return false;
            }
            int sum = 0;
            for(int num : nums){
        
                sum += num;
            }
            if(sum % 2 == 1){
        
                return false;
            }
            int target = sum / 2;
            int[] dp = new int[target+1];
            for(int i = 0;i<nums.length;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;
        }
    }

![在这里插入图片描述][d6fffee9e3884cfb85db9a204062e930.png]

[416.]: https://leetcode.cn/problems/partition-equal-subset-sum/
[LeetCode-39.]: https://donglin.blog.csdn.net/article/details/129132875
[4e6b1f0ec5e446a0a3feaf637f3846af.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/7948fcfcdd0b4123a3df9072d4dc9e5e.png
[https_donglin.blog.csdn.net_article_details_129412502]: https://donglin.blog.csdn.net/article/details/129412502
[f0acb01492e24f8893341fb318266f6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/898d3ff9f08c4336ade1b62d84145e03.png
[https_donglin.blog.csdn.net_article_details_129437136]: https://donglin.blog.csdn.net/article/details/129437136
[31f75fbef4aa4af695a4f664a76e4214.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/9040be72d2a340c1b70fe990d87b057c.png
[d6fffee9e3884cfb85db9a204062e930.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/6178fe25de234a8aa2720053673b2f68.png