学步园

某小盆友给的题。

给你一串数，让你通过增加加号或者减号使得经过运算得到另外一个数，问有多少种方法。

我的做法是枚举每个参与运算的数，DFS下就好。注意第一个数前面不能有符号。

#include <stdio.h>
#include <string.h>
char s[15];
int sum,len;
__int64  n;
void DFS(int x, __int64 ans)
{
	if( x == len )
	{
		if( ans == n )
			sum++;
		return ;
	}
	__int64 k = 0;	
	for(int i=x; i<len; i++)
	{
		k = k*10 + s[i] - '0';
		DFS(i+1, ans + k);
		if( x != 0 ) DFS(i+1, ans - k);
	}
}

int main()
{
	while( ~scanf("%s", s) )
	{
		scanf("%I64d", &n);
		len = strlen(s);
		sum = 0;
		DFS(0, 0);
		printf("%I64d\n",sum);
	}
return 0;
}