【LeetCode 热题 100】416. 分割等和子集——（解法一）记忆化搜索
Problem: 416. 分割等和子集
文章目录
- 整体思路
- 完整代码
- 时空复杂度
- 时间复杂度：O(N * target) 或 O(N * sum)
- 空间复杂度：O(N * target) 或 O(N * sum)
整体思路
这段代码旨在解决经典的 “分割等和子集” (Partition Equal Subset Sum) 问题。问题要求判断一个给定的、只包含正整数的数组 nums 是否可以被分割成两个子集，使得这两个子集的元素和相等。
该算法将原问题巧妙地转化为一个 0/1 背包问题，并采用 自顶向下（Top-Down）的动态规划，即 记忆化搜索 (Memoization) 来求解。
-
问题转化：0/1 背包模型
- 核心洞察：如果一个数组可以被分割成两个和相等的子集，那么每个子集的和必然等于数组总和的一半。
- 初步检查：因此，算法首先计算数组的总和
sum。如果sum是奇数，那么它不可能被平分成两个整数和，可以直接返回false。 - 新问题：如果
sum是偶数，问题就转化为：能否从nums数组中挑选出若干个数字，使得它们的和恰好等于target = sum / 2？ 如果能找到这样一个子集，那么剩下的数字自然也构成一个和为target的子集。 - 背包类比：
- 背包容量：
target。 - 物品：
nums数组中的每一个数字。 - 物品重量：
nums[i]的值。 - 目标：能否恰好装满背包（即子集和等于
target）。 - “0/1”：每个数字（物品）只有两种选择：选入子集或不选入子集，不能重复使用。
- 背包容量：
-
状态定义与递归关系
- 算法的核心是递归函数
dfs(i, target)，其状态定义为：
dfs(i, target)= 在只考虑前i+1个数字（从nums[0]到nums[i]）的情况下，是否能凑出和为target。 - 对于当前考虑的数字
nums[i]，我们有两个选择：
a. 不选nums[i]：如果我们不把它放入子集，问题就变成了“用前i个数字（nums[0]到nums[i-1]）能否凑出target”，这对应于递归调用dfs(i - 1, target, ...)。
b. 选nums[i]：如果我们把它放入子集（前提是target >= nums[i]），问题就变成了“用前i个数字能否凑出target - nums[i]”，这对应于dfs(i - 1, target - nums[i], ...)。 - 只要这两种选择中有任何一种能成功（返回
true），dfs(i, target)的结果就是true。
- 算法的核心是递归函数
-
记忆化与基础情况
- 记忆化：使用二维数组
memo存储子问题的解。memo[i][target]记录dfs(i, target)的结果（用1表示true，0表示false），避免重复计算。 - 基础情况：
if (i < 0)是递归的出口。当没有数字可选时，只有当target恰好也为0时，才算成功。
- 记忆化：使用二维数组
完整代码
import java.util.Arrays;class Solution {/*** 判断数组是否可以被分割成两个和相等的子集。* @param nums 只包含正整数的数组* @return 如果可以分割则返回 true，否则返回 false*/public boolean canPartition(int[] nums) {// 1. 计算数组总和int sum = 0;for (int num : nums) {sum += num;}// 2. 如果总和为奇数，不可能平分，直接返回 falseif (sum % 2 == 1) {return false;}int n = nums.length;// 3. 确定目标和（背包容量）int target = sum / 2;// 4. 初始化记忆化数组// memo[i][j] 存储用前 i+1 个数能否凑成 j 的结果// -1: 未计算, 0: false, 1: trueint[][] memo = new int[n][target + 1];for (int[] row : memo) {Arrays.fill(row, -1);}// 5. 从最后一个元素开始，启动递归求解return dfs(n - 1, target, nums, memo);}/*** 记忆化搜索函数* @param i 当前考虑的数字的索引* @param target 当前需要凑成的目标和* @param nums 原始数组* @param memo 记忆化数组* @return 是否能凑成 target*/private boolean dfs(int i, int target, int[] nums, int[][] memo) {// 基础情况：如果没有数字可选了if (i < 0) {// 如果此时 target 恰好为 0，说明找到了一组解；否则失败。return target == 0;}// 记忆化检查：如果该子问题已计算过，直接返回结果。if (memo[i][target] != -1) {return memo[i][target] == 1;}// 状态转移：// 结果 res 为 true 的条件是以下两者之一为 true：// 1. (target >= nums[i] && dfs(i-1, ...)): 选择 nums[i] 的情况，前提是 target 足够大，// 并且剩余的数字能凑成 target - nums[i]。// 2. dfs(i-1, ...): 不选择 nums[i] 的情况，剩余的数字需要凑成完整的 target。boolean res = (target >= nums[i] && dfs(i - 1, target - nums[i], nums, memo)) || dfs(i - 1, target, nums, memo);// 将计算结果存入 memo 数组（1 for true, 0 for false）memo[i][target] = res ? 1 : 0;return res;}
}
时空复杂度
时间复杂度：O(N * target) 或 O(N * sum)
N是数组nums的长度。target是数组总和的一半。
- 状态数量：由于记忆化的存在，每个状态
(i, target)只会被实际计算一次。i的范围是从0到N-1（共N种）。target的范围是从0到sum/2（共target + 1种）。- 因此，总的状态数量是
N * (target + 1)。
- 每个状态的计算时间：在
dfs函数内部，除了递归调用，其他的操作都是 O(1) 的。
综合分析：
总的时间复杂度等于（状态数量）×（每个状态的计算时间），即 O(N * target)。由于 target 与 sum 是线性关系，也可以写作 O(N * sum)。
空间复杂度：O(N * target) 或 O(N * sum)
- 记忆化数组：算法创建了一个
memo二维数组来存储所有子问题的解。其大小为N * (target + 1)。这部分空间占用为 O(N * target)。 - 递归调用栈：递归的深度也需要考虑。在最坏的情况下，例如
dfs(n-1, target)一路调用dfs(n-2, ...)直到dfs(-1, ...)，递归深度可达N。因此，递归栈所占用的空间是 O(N)。 - 综合分析：
- 记忆化数组的空间开销是 O(N * target)。
- 递归栈的空间开销是 O(N)。
- 由于
target通常远大于1，N * target是主导项。因此最终的空间复杂度为 O(N * target)。
参考灵神