思路分析

问题的转换

首先，我们可以把问题转化为一个经典的子集和问题。我们需要找到数组中所有的子序列，其元素和等于数组所有元素和的 $\frac{1}{2}$。因此，我们首先需要计算出数组的总和 $S$，然后检查是否存在某些子序列使得它们的和恰好是 $\frac{S}{2}$。

关键点

1. 总和为奇数时，显然不可能找到一个子序列的和恰好是 $\frac{S}{2}$，因为没有办法将一个奇数分成两个整数部分。
2. 子集和问题，可以使用动态规划来解决。我们可以通过动态规划的方法，计算所有可能的子集和，并记录出现的次数。

动态规划实现

定义 $dp[x]$ 为能够得到和为 $x$ 的子集的个数。初始状态是 $dp[0] = 1$，即空子集的和为 $0$。接下来，我们遍历数组中的每一个数，对于每个数 $num$，我们更新 $dp$ 数组，表示新的子集和的个数。

算法步骤

1. 计算数组的总和 $S$。
2. 如果 $S$ 是奇数，输出 0，因为无法找到一个子集和为 $\frac{S}{2}$。
3. 否则，使用动态规划方法计算和为 $\frac{S}{2}$ 的子集个数。

动态规划转移

对于每一个数 $num$，从大到小更新 $dp$ 数组：

dp[j] = dp[j] + dp[j - num]

这样可以保证每个数在计算时只被使用一次。

时间复杂度

假设数组长度为 $n$，最大总和为 $S$，那么时间复杂度是 $O(n \times S)$，其中 $S$ 是数组的总和的一半。由于 $S \leq 100,000$，所以时间复杂度可以接受。

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    int sum = 0;
    
    // 读取数组并计算总和
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        sum += arr[i];
    }

    // 如果总和是奇数，直接输出 0
    if (sum % 2 != 0) {
        cout << 0 << endl;
        return 0;
    }

    // 动态规划数组，求和为 sum / 2 的子集个数
    int target = sum / 2;
    vector<int> dp(target + 1, 0);
    dp[0] = 1;  // 空集和为 0

    // 动态规划更新 dp 数组
    for (int i = 0; i < n; ++i) {
        for (int j = target; j >= arr[i]; --j) {
            dp[j] += dp[j - arr[i]];
        }
    }

    // 输出结果，即和为 target 的子集个数
    cout << dp[target] << endl;
    
    return 0;
}

Python

def count_subsequences(arr):
    total_sum = sum(arr)
    
    # 如果总和是奇数，直接返回 0
    if total_sum % 2 != 0:
        return 0
    
    target = total_sum // 2
    dp = [0] * (target + 1)
    dp[0] = 1  # 空子集和为 0
    
    # 动态规划更新 dp 数组
    for num in arr:
        for j in range(target, num - 1, -1):
            dp[j] += dp[j - num]
    
    return dp[target]

# 读取输入
n = int(input())
arr = list(map(int, input().split()))

# 输出结果
print(count_subsequences(arr))

Java

import java.util.Scanner;

public class Main {
    public static int countSubsequences(int[] arr) {
        int totalSum = 0;
        for (int num : arr) {
            totalSum += num;
        }
        
        // 如果总和是奇数，直接返回 0
        if (totalSum % 2 != 0) {
            return 0;
        }
        
        int target = totalSum / 2;
        int[] dp = new int[target + 1];
        dp[0] = 1;  // 空子集和为 0
        
        // 动态规划更新 dp 数组
        for (int num : arr) {
            for (int j = target; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        
        return dp[target];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 输出结果
        System.out.println(countSubsequences(arr));
    }
}

题目大意

给定一个大小为n的数组，请问存在多少种方案的子序列使得该子序列的和是原数组元素总和的一半。

样例输入

输入

4
1 2 3 4

输出

2

数据范围

$1 \le n \le 200$ 数组元素大于0且其总和不超过 $1e5$ , 保证方案总数不超过int的最大值。