当前位置：首页 > news >正文

【Leetcode 热题 100】416. 分割等和子集

news 来源：原创 2025/5/18 3:45:24

问题背景

给你一个 只包含正整数 的非空数组 $n u m s$ 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

数据约束

$\le nums.length \le 200$
$\le nums[i] \le 100$

解题过程

要求分成两个子集且和相等，其实就是找到一个总和为 $s u m /2$ 的子集，其中 $s u m$ 表示整个集合的和。需要注意的是， $s u m$ 必须是偶数。
此外，和为零是一种可能的状态，所以记忆化数组中的元素要初始化为 $- 1$ 。
递归入口是 $df s (n - 1, s u m /2)$ ，表示在 $[0, n - 1]$ 的范围上找到一个和为 $s u m /2$ 的子集。
递归边界是 $df s (- 1, 0) = t r u e$ ，表示枚举完了整个集合中的所有元素，最终能够使得剩余目标和减少到零。

翻译成递推时要注意，数组下标不能为 $- 1$ ，所以要进行转移，将结果映射到 $[1, n]$ 这个范围上。

具体实现

递归

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if ((sum & 1) == 1) {return false;}int n = nums.length;int[][] memo = new int[n][(sum >> 1) + 1];for (int[] row : memo) {Arrays.fill(row, -1);}return dfs(n - 1, sum >> 1, nums, memo);}private boolean dfs(int i, int j, int[] nums, int[][] memo) {if (i < 0) {return j == 0;}if (memo[i][j] != -1) {return memo[i][j] == 1;}boolean res = j >= nums[i] && dfs(i - 1, j - nums[i], nums, memo) || dfs(i - 1, j, nums, memo);memo[i][j] = res ? 1 : 0;return res;}
}

递推

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if ((sum & 1) == 1) {return false;}sum /= 2;int n = nums.length;boolean[][] dp = new boolean[n + 1][sum + 1];dp[0][0] = true;for (int i = 0; i < n; i++) {int cur = nums[i];for (int j = 0; j <= sum; j++) {dp[i + 1][j] = j >= cur && dp[i][j - cur] || dp[i][j];}}return dp[n][sum];}
}

空间优化

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if ((sum & 1) == 1) {return false;}sum /= 2;int n = nums.length;boolean[] dp = new boolean[sum + 1];dp[0] = true;// minSum 表示前 i 个数和的上界，不可能超过所有这些数的总和int minSum = 0;for (int num : nums) {// 用这个值来初始化内层循环可以避免许多不必要的判断，想不清楚的话直接用 sum 也可以minSum = Math.min(minSum + num, sum);for (int j = minSum; j >= num; j--) {dp[j] = dp[j] || dp[j - num];}if (dp[sum]) {return true;}}return false;}
}

问题背景

数据约束

解题过程

具体实现

递归

递推

空间优化

相关文章：