Two Sets II 题解

题目描述

https://cses.fi/problemset/task/1092

给定数字 1, 2, …, n，求将其分成两个和相等集合的方式数。

限制：

• 1 ≤ n ≤ 500

示例：

• 输入：7
• 输出：4
• 解释：
  • {1,3,4,6} 和 {2,5,7}
  • {1,2,5,6} 和 {3,4,7}
  • {1,2,4,7} 和 {3,5,6}
  • {1,6,7} 和 {2,3,4,5}

---

解法

问题类型：0-1 背包（每个数字只能用一次，求方案数）

分析：

• 数字 1~n 的总和为 $S = n(n+1)/2$
• 如果 S 为奇数，无法平分，输出 0
• 如果 S 为偶数，目标是在一半和 $S/2$ 内放入一些数字

定义：dp[j] 为凑成和 j 的方式数

初始条件：dp[0] = 1（和为 0 有一种方式：什么都不选）

状态转移：

$$dp[j] = dp[j] + dp[j - i] \quad \text{for all } i \text{ (倒序)}$$

解释：遍历数字 1~n-1（最后数字 n 必须放在较大的一组，所以只用 1~n-1），尝试将每个数字加入集合中。倒序遍历确保每个数字只用一次。

代码

import sys

MOD = 10**9 + 7

n = int(input())

sum_elem = n * (n + 1) // 2

if sum_elem % 2 == 1:
    print(0)
    sys.exit()

target = sum_elem // 2

dp = [0] * (target + 1)
dp[0] = 1

for i in range(1, n):
    for j in range(target, i - 1, -1):
        dp[j] = (dp[j] + dp[j - i]) % MOD

print(dp[target])

时间复杂度：O(n × target)
空间复杂度：O(target)

注意：只需遍历 1~n-1，因为数字 n 必须放在较大的一组（如果总和是偶数，较大的那组一定包含 n）。

---

算法详解

为什么只用 1~n-1？

设总和为 $S = n(n+1)/2$，目标值为 $S/2$。

• 假设 n 在较小的那组，那么较小那组的最大可能和为 $1+2+…+(n-1) = n(n-1)/2$
• 由于 $S/2 = n(n+1)/4 > n(n-1)/4$，所以 n 不可能在较小的那组
• 因此 n 一定在较大的那组，只需用 1~n-1 来凑成 S/2

示例

n = 7，总和 = 28，目标 = 14

用数字 1~6 凑成 14 的方式：

{1,3,4,6} = 14
{1,2,5,6} = 14
{1,2,4,7} 错误（7 超出范围）
{1,6,7}    错误（7 超出范围）

实际上用 1~6 凑 14 的 4 种方式，加上数字 7，就是 4 种分组方式。