时间轴

2026-03-21

init

题目：

P416 分割等和子集

https://leetcode.cn/problems/partition-equal-subset-sum/?envType=study-plan-v2&envId=top-100-liked

将子数组求和，然后将和除以2，转化找到数组一个子集为总和的一半，即为 0-1 背包问题

dp[i][j] 表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于 j。初始时，dp 中的全部元素都是 false。

初始化：

  • 如果不选取任何正整数，则被选取的正整数之和等于 0。因此对于所有 0 ≤ i < n，都有 dp[i][0]=true。
  • 当 i==0 时，只有一个正整数 nums[0] 可以被选取，因此 dp[0]nums[0]]=true。

状态转移：

  • dp[i][j] = dp[i−1][j] ∣ dp[i−1][j−nums[i]] (j >= nums[i])
  • dp[i][j] = dp[i-1][j] (j < nums[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <vector>
using std::vector;

class Solution {
    public:
        bool canPartition(vector<int> &nums)
        {
                int i, j, n = nums.size();
                int sum = 0, target;

                for (i = 0; i < n; i++)
                        sum += nums[i];

                if (sum % 2 != 0) // 奇数
                        return false;

                target = sum / 2;

                for (i = 0; i < n; i++) { // 有一个数超过总和的一半
                        if (nums[0] > target)
                                return false;
                }

                // 0-1 背包问题
                // dp[i][j] 表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是 0 个）
                // 是否存在一种选取方案使得被选取的正整数的和等于 j。初始时，dp 中的全部元素都是 false。
                vector<vector<bool> > dp(n, vector<bool>(target + 1, false));

                // 如果不选取任何正整数，则被选取的正整数之和等于 0。因此对于所有 0 ≤ i < n，都有 dp[i][0]=true。
                for (i = 0; i < n; i++)
                        dp[i][0] = true;
                // 当 i==0 时，只有一个正整数 nums[0] 可以被选取，因此 dp[0][nums[0]]=true。
                dp[0][nums[0]] = true;

                // dp[i][j] = dp[i−1][j] ∣ dp[i−1][j−nums[i]] (j >= nums[i])
                // dp[i][j] = dp[i-1][j] (j < nums[i])
                for (i = 1; i < n; i++) {
                        for (j = 1; j <= target; j++) {
                                if (j >= nums[i])
                                        dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]];
                                else
                                        dp[i][j] = dp[i - 1][j];
                        }
                }

                return dp[n - 1][target];
        }
};