题目链接
2469: C 小Y的难题（1）
Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submit: 9 Accepted: 7 Page View: 128
Submit Status Discuss
Description
最近小Y迷上了数学，总是在思考各种数学问题。有一天，他不小心把墨水洒在草稿纸上。他现在能看到的是“2?3?1?4”（？表示看不清的地方）。小Y的记忆力不错，他知道：
1、每个？只会是“+”、“-”，“=”三个符号之一。
2、总共有且仅有一个“=”。
3、原式一定是一个等式。如“2+3-1=4”
现在他突然想知道，有多少种可能性，满足上面3个要求。
Input
多组输入。
每组第一行有一个数字n。表示小Y从左到右，一共可以看到n个数字。（2<=n<=15）
每组第二行有n个数字。分别表示这n个数字是什么。保证每个数字都是非负整数，且小于10^7。
Output
对于每组，输出一行，这一行只有一个数字，表示有多少种可能性满足题意。
Sample Input
Raw
4
2 3 1 4
4
1 1 1 1
Sample Output
Raw
2
6
Hint
数字之间一定有且仅有一个符号，第一个数字前没有符号。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[25];
int n;
int ans=0;
void DFS(int sum,int num,int c)//num表示要处理的第几个数
{
if(num==n)
{
if(sum==0)
ans+=c;
return ;
}
DFS(sum+a[num], num+1, c);
DFS(sum-a[num], num+1,c+1);
}
int main ()
{
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
ans=0;
DFS(a[0],1,0);
printf("%d\n",ans);
}
return 0;
}