[USACO2.2] 集合 Subset Sums

题意

把集合 $\{1,2,\ldots,N\}$ 划分成两个子集，使两个子集的元素和相等，求划分方案数。交换两个子集视为同一种划分（即不区分左右）。若无法平分则输出 $0$ 。

$1\le N\le 39$ 。

思路

一句话本质：把 $1$ 到 $N$ 分成和相等的两堆，等价于从 $\{1,\ldots,N\}$ 中选一个子集使和为 $total/2$ ，选法数除以 $2$ 就是答案。

两个子集和相等，意味着什么约束？

设数列总和 $total = 1+2+\cdots+N = N(N+1)/2$ 。若划分后两边和相等，每边和一定是 $total/2$ 。因此如果 $total$ 是奇数，答案直接为 $0$ ——整数和不可能平分。

如果 $total$ 是偶数，问题转化成什么？

设 $target = total/2$ 。只要从 $\{1,\ldots,N\}$ 中选出一个子集，其和为 $target$ ，那么剩余的元素组成的子集和也是 $target$ ，这就构成了一种划分。反过来，任意一种平分划分都唯一对应这样一个和为 $target$ 的子集。

于是问题变成：从 $1$ 到 $N$ 的整数中各数最多用一次，选若干个数使和恰好为 $target$ ，有多少种选法？

计数怎么用 DP 做？

这是一个标准的 0/1 背包计数问题。设 $dp[j]$ 表示从已处理的数中选出若干，使得和恰好为 $j$ 的方案数。

初始化 $dp[0]=1$ （空集和为 $0$ ，一种方案）。依次处理每个数 $i$ （ $1$ 到 $N$ ），倒序更新：

dp[j] = dp[j] + dp[j-i]

$dp[j-i]$ 表示"不含 $i$ 时和为 $j-i$ 的方案数"，加上 $i$ 就得到和为 $j$ 的新方案。倒序保证每个 $i$ 在每个方案中最多用一次。

算出 $dp[target]$ 后为什么还要除 $2$ ？

因为上述过程算出来的是"选出一个和为 $target$ 的子集"的方案数。对于每一种划分，它对应的子集可以是左边那堆也可以是右边那堆，这两者被当作两种"选子集"方案统计了。由于题目不区分左右，所以最终答案要除以 $2$ 。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXS = 400;

int n;
// dp[j] 表示从 1..n 中选若干不同的数，和为 j 的子集个数。
ll dp[MAXS * MAXS];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    int total = n * (n + 1) / 2;
    if (total % 2 != 0) {                // 总和为奇数无法平分为两个相等子集
        cout << 0 << '\n';
        return 0;
    }

    int target = total / 2;

    // 0/1 背包计数：dp[0]=1，每个数 i 只能用一次，倒序枚举。
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = target; j >= i; j--) {
            dp[j] += dp[j - i];
        }
    }

    // 每种集合划分算了两次（左右交换），除以 2。
    cout << dp[target] / 2 << '\n';
    return 0;
}

复杂度

时间复杂度： $O(N \cdot target) = O(N^3)$ ， $N\le 39$ 时 $target\le 390$ ，完全可行
空间复杂度： $O(target)$

总结

本题的关键翻译是：“分成两个和相等的子集” → “找一个和为 $total/2$ 的子集”。一旦完成这个等价转换，就变成了 0/1 背包计数。最后记住除以 $2$ 去掉左右对称的重复计数。

[USACO2.2] 集合 Subset Sums

目录

题意

思路

代码

复杂度

总结