Partition Equal Subset Sum

416. 分割等和子集

分析

典型的 01 背包问题，我们需要判断是否存在一个子集，其元素和为 sum / 2，其中 sum 是数组 nums 的元素总和

特殊情况处理：
- 如果数组总和 sum 是奇数，则无法分成两个相等的子集，直接返回 false
动态规划定义：
- 定义一个布尔数组 f，其中 f[j] 表示是否可以从数组中选取一些元素，使得这些元素的和为 j
- 初始化 f[0] = true，表示总和为 0 的情况总是成立（即不选任何元素）
状态转移方程：
- 遍历数组 nums 中的每个数 nums[i]，从目标值 target 开始往下更新：
  - f[j] = f[j] || f[j - nums[i]]
- 表示如果在之前能凑出 j - nums[i]，则加入当前数字后也能凑出 j
最终结果：
- 如果能凑出目标值 sum / 2，即 f[target] == true，则可以分成两个相等的子集

时间复杂度

外层循环遍历数组 n 次
内层循环遍历目标值 target 次

总时间复杂度 O(n * target)

空间复杂度

空间复杂度为 O(target)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution
{
public:
    bool canPartition(vector<int>& nums)
    {
        int sum = 0;
        for (int num : nums)  // 计算数组的总和
            sum += num;

        if (sum % 2)  // 如果总和是奇数，无法分割成两个相等的子集
            return false;

        int target = sum / 2;  // 目标子集的和
        int n = nums.size();
        std::vector<bool> f(target + 1, false);  // 定义状态数组，f[j] 表示是否可以凑出总和 j
        f[0] = true;  // 总和为 0 的情况成立

        for (int i = 0; i < n; ++i)  // 遍历每个数
            for (int j = target; j >= nums[i]; --j)  // 从 target 向下遍历，避免状态覆盖
                f[j] = f[j] || f[j - nums[i]];

        return f[target];  // 返回是否可以凑出目标总和
    }
};