TZOJ A and B Problem

描述

相信你已经AC了A + B Problem，是不是很简单呢。

下面继续A and B Problem这个简单的问题，将若干个长度不同的木棍，分成A堆和B堆，并且保证A堆所有木棍的长度之和等于B堆所有木棍的长度之和。

输入

输入数据有多组。

每组测试数据第一行为一个正整数n(n<=100)，代表总的木棍个数；

第二行为n个以空格隔开的正整数ci(ci<=100)。

输出

如果n根木棍可以分成两堆木棍（A堆和B堆），并且A堆所有木棍的长度之和等于B堆所有木棍的长度之和，则输出"Yes" ,否则输出"No"（A堆和B堆中的木棍个数不必相等）。

样例输入

4
1 2 3 4
2
1 2

样例输出

Yes
No

解题思路

用深搜索+回溯就可以了

代码

#include<bits/stdc++.h>
using namespace std;
int a[105];
bool vis[105],flog;
int n;
void dfs(int s)
{
    if(flog) return;if(s==0){
    flog=1;return;}for(int i=0;i<n;i++){
    if(!vis[i]&&s>=a[i]){
    vis[i]=1;dfs(s-a[i]);vis[i]=0;}}
}
int main()
{
    while(~scanf("%d",&n)){
    int sum=0;flog=0;memset(vis,0,sizeof(vis));for(int i=0;i<n;i++){
    scanf("%d",&a[i]);sum+=a[i];}///sort(a,a+n);if(sum%2!=0)printf("No\n");else{
    dfs(sum/2);if(flog)printf("Yes\n");else printf("No\n");}}
}