Python 巧解：统计集合中可平分的子集数量

以下是使用 Python 实现的解决方案： ```python n = int(input()) # 读取集合元素 nums = list(map(int, input().split())) # 初始化可平分的子集数量 count = 0 # 遍历所有可能的子集 for i in range(1 << n): subset = [] for j in range(n): if (i >> j) & 1: subset.append(nums[j]) # 空集也算可平分的 if len(subset) == 0: count += 1 continue total = sum(subset) # 如果子集元素和为奇数，肯定不能平分 if total % 2 != 0: continue target = total // 2 dp = [False] * (target + 1) dp[0] = True for num in subset: for j in range(target, num - 1, -1): dp[j] = dp[j] or dp[j - num] if dp[target]: count += 1 print(count) ``` 代码解释： 1. 读取输入：首先读取集合的大小 `n`，然后读取集合的元素并存储在列表 `nums` 中。 2. 遍历所有子集：使用位运算遍历集合的所有子集。对于每个子集，我们将其元素添加到 `subset` 列表中。 3. 处理空集：空集也算可平分的，所以如果子集为空，直接将可平分子集数量 `count` 加 1。 4. 判断子集是否可平分： - 计算子集元素的总和 `total`。如果总和为奇数，那么该子集肯定不能平分，跳过该子集。 - 计算目标和 `target`，即总和的一半。 - 使用动态规划来判断是否存在子集的和等于 `target`。如果存在，则说明该子集是可平分的，将 `count` 加 1。 5. 输出结果：最后输出可平分的子集数量。 复杂度分析： - 时间复杂度：$O(2^n \times S)$，其中 $n$ 是集合的大小，$S$ 是子集元素的最大和。 - 空间复杂度：$O(S)$，主要用于动态规划数组。 ######[AI问答 | 533点数解答 | 2025-12-13 10:33:40]