题目

给出一个有 $N$ 个元素的集合 $A$，求 $A$ 有几个子集合可以分为两部分，使得这两部分和相等。注 空集也算。

数据范围

$N \le 20,A_i \le 10^7$

蒟蒻丑陋的 $O(2^NN)$ 的代码

#include "bits/stdc++.h"
using namespace std ;
const int N = 22 ;
int Nlist[N] ;
int n, a[N], ans ;
inline void Dfs(int v, int c, int *sum)
{
	sum[c] = sum[c - 1] + a[v] ;
	int sum2 = 0 ;
	for(int i = c ; i >= 1 ; --i)
	{
		sum2 += sum[i] - sum[i - 1] ;
		if(sum[i - 1] == sum2)
		{
			cout << i << "|" << sum2 << endl ;
			ans++ ;
			break ;
		}
	}
	if(v >= N) return ;
	for(int i = v + 1 ; i <= n ; ++i)
	{
		Dfs(i, c + 1, sum) ;
	}
	Dfs(N, c + 1, sum) ;
}
int main()
{
	ios::sync_with_stdio(false) ;
	cin.tie(0) ; cout.tie(0) ;
	cin >> n ;
	for(int i = 1 ; i <= n ; ++i) cin >> a[i] ;
	Dfs(0, 0, Nlist) ;
	cout << ans + 1 << endl ;
	return 0 ;
}