题目链接 · 灵神原题解（署名来源）

一、分析

设 $\mathit{\text{nums}}$ 的元素和为 $s$。

两个子集的元素和相等，意味着：

1. 把 $\mathit{\text{nums}}$ 分成两个子集，每个子集的元素和恰好等于 ${\displaystyle \frac{s}{2}}$。
2. $s$ 必须是偶数。

如果 $s$ 是奇数，${\displaystyle \frac{s}{2}}$ 不是整数，直接返回 $\mathtt{\text{false}}$。

如果 $s$ 是偶数，问题相当于：

• 能否从 $\mathit{\text{nums}}$ 中选出一个子序列，其元素和恰好等于 ${\displaystyle \frac{s}{2}}$？

这可以用「恰好装满」型 0-1 背包解决，请看视频讲解：0-1 背包和完全背包【基础算法精讲 18】。制作不易，欢迎点赞关注~

二、记忆化搜索

定义 $\mathit{\text{dfs}}(i,j)$ 表示能否从 $\mathit{\text{nums}}[0]$ 到 $\mathit{\text{nums}}[i]$ 中选出一个和恰好等于 $j$ 的子序列。

考虑 $\mathit{\text{nums}}[i]$ 选或不选：

• 选（前提是 $j\ge \mathit{\text{nums}}[i]$）：问题变成能否从 $\mathit{\text{nums}}[0]$ 到 $\mathit{\text{nums}}[i-1]$ 中选出一个和恰好等于 $j-\mathit{\text{nums}}[i]$ 的子序列，即 $\mathit{\text{dfs}}(i-1,j-\mathit{\text{nums}}[i])$。
• 不选：问题变成能否从 $\mathit{\text{nums}}[0]$ 到 $\mathit{\text{nums}}[i-1]$ 中选出一个和恰好等于 $j$ 的子序列，即 $\mathit{\text{dfs}}(i-1,j)$。

这两个只要有一个成立，$\mathit{\text{dfs}}(i,j)$ 就是 $\mathtt{\text{true}}$。所以有

$$\mathit{\text{dfs}}(i,j)=\{\begin{array}{ll}\mathit{\text{dfs}}(i-1,j),& j<\mathit{\text{nums}}[i]\\ \mathit{\text{dfs}}(i-1,j-\mathit{\text{nums}}[i])\vee \mathit{\text{dfs}}(i-1,j),& j\ge \mathit{\text{nums}}[i]\end{array}$$

这里 $\vee$ 相当于编程语言中的 ||。

递归边界：$\mathit{\text{dfs}}(-1,0)=\mathtt{\text{true}},\mathit{\text{dfs}}(-1,>0)=\mathtt{\text{false}}$。注意 $j$ 是从 $s/2$ 开始倒着减的，如果 $j$ 能减小成恰好等于 $0$，就表示找到了一个和恰好等于 $s/2$ 的子序列。

递归入口：$\mathit{\text{dfs}}(n-1,s/2)$，即答案。

答疑

问：是否需要在递归中途判断 $j=0$ 的情况，提前返回？

答：可以，但没有必要。因为我们有记忆化，这些 $j=0$ 的状态只会计算一次。只有第一次遇到 $j=0$ 的时候会往下递归到 $i<0$，后面是不会重复递归到 $i<0$ 的情况的。

问：什么情况下，返回值是布尔类型，什么情况下是整型？

答：通常来说，判断能不能的问题，返回值是布尔类型；计算最大、最小、方案数等问题，返回值是整型。

写法一

Python 解法1

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return j == 0
            if j < nums[i]:
                return dfs(i - 1, j)  # 只能不选
            return dfs(i - 1, j - nums[i]) or dfs(i - 1, j)  # 选或不选

        s = sum(nums)
        return s % 2 == 0 and dfs(len(nums) - 1, s // 2)

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int s = reduce(nums.begin(), nums.end());
        if (s % 2) {
            return false;
        }
        
        int n = nums.size();
        vector memo(n, vector<int>(s / 2 + 1, -1)); // -1 表示没有计算过

        // lambda 递归函数
        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) {
                return j == 0;
            }

            int& res = memo[i][j]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }

            if (j < nums[i]) {
                return res = dfs(i - 1, j); // 只能不选
            }
            return res = dfs(i - 1, j - nums[i]) || dfs(i - 1, j); // 选或不选
        };

        return dfs(n - 1, s / 2);
    }
};

写法二

简化了 $\mathtt{\text{dfs}}$ 的返回逻辑，方便下面翻译成递推。

Python 解法3

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int) -> bool:
            if i < 0:
                return j == 0
            return j >= nums[i] and dfs(i - 1, j - nums[i]) or dfs(i - 1, j)

        s = sum(nums)
        return s % 2 == 0 and dfs(len(nums) - 1, s // 2)

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int s = reduce(nums.begin(), nums.end());
        if (s % 2) {
            return false;
        }
        
        int n = nums.size();
        vector memo(n, vector<int>(s / 2 + 1, -1)); // -1 表示没有计算过

        // lambda 递归函数
        auto dfs = [&](this auto&& dfs, int i, int j) -> bool {
            if (i < 0) {
                return j == 0;
            }

            int& res = memo[i][j]; // 注意这里是引用
            if (res != -1) { // 之前计算过
                return res;
            }

            res = j >= nums[i] && dfs(i - 1, j - nums[i]) || dfs(i - 1, j);
            return res;
        };

        return dfs(n - 1, s / 2);
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(ns)$，其中 $n$ 是 $\mathit{\text{nums}}$ 的长度，$s$ 是 $\mathit{\text{nums}}$ 的元素和（的一半）。由于每个状态只会计算一次，动态规划的时间复杂度 $=$ 状态个数 $\times$ 单个状态的计算时间。本题状态个数等于 $\mathcal{O}(ns)$，单个状态的计算时间为 $\mathcal{O}(1)$，所以动态规划的时间复杂度为 $\mathcal{O}(ns)$。
• 空间复杂度：$\mathcal{O}(ns)$。保存多少状态，就需要多少空间。

三、1:1 翻译成递推

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体来说，$f[i][j]$ 的定义和 $\mathit{\text{dfs}}(i,j)$ 的定义是一样的，都表示能否从 $\mathit{\text{nums}}[0]$ 到 $\mathit{\text{nums}}[i]$ 中选出一个和恰好等于 $j$ 的子序列。

相应的递推式（状态转移方程）也和 $\mathit{\text{dfs}}$ 一样：

$$f[i][j]=\{\begin{array}{ll}f[i-1][j],& j<\mathit{\text{nums}}[i]\\ f[i-1][j-\mathit{\text{nums}}[i]]\vee f[i-1][j],& j\ge \mathit{\text{nums}}[i]\end{array}$$

但是，这种定义方式没有状态能表示递归边界，即 $i=-1$ 的情况。

解决办法：在二维数组 $f$ 的最上边插入一排状态，那么其余状态全部向下偏移一位，把 $f[i]$ 改为 $f[i+1]$，把 $f[i-1]$ 改为 $f[i]$。

修改后，$f[i+1][j]$ 表示能否从 $\mathit{\text{nums}}[0]$ 到 $\mathit{\text{nums}}[i]$ 中选出一个和为 $j$ 的子序列。$f[0]$ 对应递归边界。

修改后的递推式为

$$f[i+1][j]=\{\begin{array}{ll}f[i][j],& j<\mathit{\text{nums}}[i]\\ f[i][j-\mathit{\text{nums}}[i]]\vee f[i][j],& j\ge \mathit{\text{nums}}[i]\end{array}$$

问：为什么 $\mathit{\text{nums}}$ 的下标不用变？

答：既然是在 $f$ 的最上边插入一排状态，那么就只需要修改和 $f$ 有关的下标，其余任何逻辑都无需修改。或者说，如果把 $\mathit{\text{nums}}[i]$ 也改成 $\mathit{\text{nums}}[i+1]$，那么 $\mathit{\text{nums}}[0]$ 就被我们给忽略掉了。

初始值 $f[0][0]=\mathtt{\text{true}}$，翻译自递归边界 $\mathit{\text{dfs}}(-1,0)=\mathtt{\text{true}}$。其余值初始化成 $\mathtt{\text{false}}$。

答案为 $f[n][s/2]$，翻译自递归入口 $\mathit{\text{dfs}}(n-1,s/2)$。

Python 解法5

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s % 2:
            return False
        s //= 2  # 注意这里把 s 减半了

        n = len(nums)
        f = [[False] * (s + 1) for _ in range(n + 1)]
        f[0][0] = True
        for i, x in enumerate(nums):
            for j in range(s + 1):
                f[i + 1][j] = j >= x and f[i][j - x] or f[i][j]
        return f[n][s]

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int s = reduce(nums.begin(), nums.end());
        if (s % 2) {
            return false;
        }
        s /= 2; // 注意这里把 s 减半了

        int n = nums.size();
        vector f(n + 1, vector<int>(s + 1));
        f[0][0] = true;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int j = 0; j <= s; j++) {
                f[i + 1][j] = j >= x && f[i][j - x] || f[i][j];
            }
        }
        return f[n][s];
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(ns)$，其中 $n$ 是 $\mathit{\text{nums}}$ 的长度，$s$ 是 $\mathit{\text{nums}}$ 的元素和（的一半）。
• 空间复杂度：$\mathcal{O}(ns)$。

四、空间优化

观察上面的状态转移方程，在计算 $f[i+1]$ 时，只会用到 $f[i]$，不会用到比 $i$ 更早的状态。

因此可以去掉第一个维度，反复利用同一个一维数组。

状态转移方程改为

$$f[j]=f[j]\vee f[j-\mathit{\text{nums}}[i]]$$

初始值 $f[0]=\mathtt{\text{true}}$。

答案为 $f[s/2]$。

具体例子，以及为什么要倒序遍历 $j$，请看 0-1 背包视频讲解。

此外，设前 $i$ 个数的和为 $s^{\prime }$，由于子序列的元素和不可能比 $s^{\prime }$ 还大，$j$ 可以从 $min(s^{\prime },s/2)$ 开始倒着枚举。比如 $\mathit{\text{nums}}$ 前两个数的和等于 $5$，那么我们无法在前两个数中，选出一个元素和大于 $5$ 的子序列，所以对于 $j>5$ 的 $f$ 值，一定是 $\mathtt{\text{false}}$，无需计算。

此外，可以在循环中提前判断 $f[s/2]$ 是否为 $\mathtt{\text{true}}$，是就直接返回 $\mathtt{\text{true}}$。

Python 解法7

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s % 2:
            return False
        s //= 2  # 注意这里把 s 减半了

        f = [True] + [False] * s
        s2 = 0
        for i, x in enumerate(nums):
            s2 = min(s2 + x, s)
            for j in range(s2, x - 1, -1):
                f[j] = f[j] or f[j - x]
            if f[s]:
                return True
        return False

C++ 解法7

// C++ 版待补充

C++ 解法8

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int s = reduce(nums.begin(), nums.end());
        if (s % 2) {
            return false;
        }
        s /= 2; // 注意这里把 s 减半了

        vector<int> f(s + 1);
        f[0] = true;
        int s2 = 0;
        for (int x : nums) {
            s2 = min(s2 + x, s);
            for (int j = s2; j >= x; j--) {
                f[j] |= f[j - x];
            }
            if (f[s]) {
                return true;
            }
        }
        return false;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(ns)$，其中 $n$ 是 $\mathit{\text{nums}}$ 的长度，$s$ 是 $\mathit{\text{nums}}$ 的元素和（的一半）。
• 空间复杂度：$\mathcal{O}(s)$。

附：bitset 做法

把布尔数组压缩成一个二进制数，二进制数从低到高第 $i$ 位是 $0$，表示布尔数组的第 $i$ 个元素是 $\mathtt{\text{false}}$；从低到高第 $i$ 位是 $1$，表示布尔数组的第 $i$ 个元素是 $\mathtt{\text{true}}$。

转移方程等价于，把 $f$ 中的每个比特位增加 $x=\mathit{\text{nums}}[i]$，即左移 $x$ 位，然后跟原来 $f$ 计算 OR。前者对应选 $x$，后者对应不选 $x$。

判断 $f[s]$ 是否为 $\mathtt{\text{true}}$，等价于判断 $f$ 的第 $s$ 位是否为 $1$，即 (f >> s & 1) == 1。

Python 解法9

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s % 2:
            return False
        s //= 2

        f = 1
        for x in nums:
            f |= f << x
        return (f >> s & 1) == 1

C++ 解法9

// C++ 版待补充

C++ 解法10

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int s = reduce(nums.begin(), nums.end());
        if (s % 2) {
            return false;
        }
        s /= 2;

        bitset<10001> f; // sum(nums[i]) / 2 <= 10000
        f[0] = 1;
        for (int x : nums) {
            f |= f << x;
        }
        return f[s]; // 判断 f 中第 s 位是否为 1
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(ns/w)$，其中 $n$ 是 $\mathit{\text{nums}}$ 的长度，$s$ 是 $\mathit{\text{nums}}$ 的元素和（的一半），$w=32$ 或者 $64$。
• 空间复杂度：$\mathcal{O}(s/w)$。

思考题

改成计算分割的方案数，要怎么做？

欢迎在评论区分享你的思路/代码。

专题训练

见下面动态规划题单的「§3.1 0-1 背包」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府