做房产中介网站,联通官网,台州网站建设seo,百家号权重查询站长工具题目链接#xff1a;416. 分割等和子集
题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集#xff0c;使得两个子集的元素和相等。
示例 1#xff1a;
输入#xff1a;nums [1,5,11,5]
输出#xff1a;true
解释#x…题目链接416. 分割等和子集
题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1
输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2
输入nums [1,2,3,5]
输出false
解释数组不能分割成两个元素和相等的子集。提示
1 nums.length 2001 nums[i] 100
文章讲解代码随想录
视频讲解动态规划之背包问题这个包能装满吗| LeetCode416.分割等和子集_哔哩哔哩_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背包问题。
