上海市计算机学会竞赛平台2023年2月月赛丙组平分数字（一）

题目描述

给定 𝑛n 个整数：𝑎1,𝑎2,⋯ ,𝑎𝑛a1​,a2​,⋯,an​，请判定能否将它们分成两个部分（不得丢弃任何数字），每部分的数字之和一样大。

输入格式

第一行：单个整数 𝑛n；
第二行：𝑛n 个整数，表示 𝑎1,𝑎2,⋯ ,𝑎𝑛a1​,a2​,⋯,an​。

输出格式

若能否平分，输出 Matched，否则输出 No

数据范围

• 对于 50%50% 的数据，1≤𝑛≤181≤n≤18；
• 对于 100%100% 的数据，1≤𝑛≤241≤n≤24；
• −10,000,000≤𝑎𝑖≤10,000,000−10,000,000≤ai​≤10,000,000

样例数据

输入:

4
1 2 3 4

输出:

Matched

说明:

1 + 4 = 2 + 3

输入:

3
2 2 2

输出:

No

详见代码:

#include<bits/stdc++.h>
using namespace std;
int n;
long long sum=0;
long long a[30];
int flag=0;
int dfs(int k,long long s)
{if (s==sum){flag=1;return 0;}if (k>n){return 0;}dfs(k+1,s);dfs(k+1,s+a[k]);
}
int main()
{cin>>n;for (int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}if (sum%2!=0){cout<<"No"<<endl;return 0;}sum/=2;dfs(1,0);if (flag==1){cout<<"Matched"<<endl;}else{cout<<"No"<<endl;}return 0;
}