本文主要是介绍【LeetCode】416. 分割等和子集(中等)——代码随想录算法训练营Day41,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:416. 分割等和子集
题目描述
给你一个 只包含正整数 的 非空 数组 nums
。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例 1:
输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2:
输入:nums = [1,2,3,5] 输出:false 解释:数组不能分割成两个元素和相等的子集。
提示:
1 <= nums.length <= 200
1 <= nums[i] <= 100
文章讲解:代码随想录
视频讲解:动态规划之背包问题,这个包能装满吗?| LeetCode:416.分割等和子集_哔哩哔哩_bilibili
题解1:回溯法(超时)
思路:使用回溯法遍历数组中每个元素是否加入到第1组中,其他元素加入到第二组,遍历所有情况看看相不相等。
/*** @param {number[]} nums* @return {boolean}*/
var canPartition = function(nums) {const path = new Array(nums.length);const backtracking = function (start) {for (let i = start; i < nums.length; i++) {path[i] = true;let sum1 = sum2 = 0;nums.forEach((num, index) => path[index] ? sum1 += num : sum2 += num);if (sum1 === sum2 || backtracking(i + 1)) {return true;}path[i] = false;}return false;};return backtracking(0);
};
分析:时间复杂度为 O(n * 2 ^ n),空间复杂度为 O(n)。
题解2:动态规划
思路:取数组元素和的一半,记为 target。以 target 为背包容量,数组的元素作为物品质量和价值,每个元素只能取1次,若能装满背包,则说明可以分割。这是一个01背包问题。
动态规划分析:
- dp 数组以及下标的含义:dp[j] 代表容量为 j 的背包最多能装下多少价值的物品。
- 递推公式:dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])。
- dp 数组初始化:全部初始化成0。
- 遍历顺序:先遍历物品,再倒序遍历背包。
- 打印 dp 数组:输入为 [1,5,11,5] 时,dp 数组为 [ 0, 1, 1, 1, 1, 5, 6, 6, 6, 6, 10, 11 ]。
/*** @param {number[]} nums* @return {boolean}*/
var canPartition = function(nums) {const target = nums.reduce((a, b) => a + b) / 2; // 背包容量为数组元素和的一半if (Math.floor(target) !== target) {return false;}const dp = new Array(target + 1).fill(0);for (let i = 0; i < nums.length; i++) {for (let j = target; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[target] === target; // 装满背包则返回 true
};
分析:时间复杂度为 O(n²),空间复杂度为 O(n)。
收获
练习动态规划法求解01背包问题。
这篇关于【LeetCode】416. 分割等和子集(中等)——代码随想录算法训练营Day41的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!