蓝桥杯省赛PREV-348试题1：算术填符号
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
匪警请拨110,即使手机欠费也可拨通！
为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！
某批警察叔叔正在进行智力训练：
1 2 3 4 5 6 7 8 9 = 110;
请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法；123+4+5+67-89 是另一个可能的答案。
请你利用计算机的优势，帮助警察叔叔快速找到所有答案。
每个答案占一行。形如：
12+34+56+7-8+9
123+4+5+67-89
......
已知的两个答案可以输出，但不计分。
各个答案的前后顺序不重要。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>//a:原先的数组 k:当前的数组的下标 s:由递归所得的字符串 goal:目标数字 void fk(int* a,int k,char* s,int goal)
{if(k == 0){if(a[0] == goal){printf("%d%s\\n",a[0],s);}//若当前下标为零，则检查是否满足goal，否则直接返回 return;}char* p=malloc(2*k + 1);memset(p,0,2*k + 1);//定义字符数组p来储存字符串 p[0] = '+';_itoa(a[k],p + 1,10); //将a[k]转换为字符储存在串中 int x = strlen(p);strcat(p + x,s);fk(a,k - 1,p,goal - a[k]);p[0] = '-';fk(a,k - 1,p,goal + a[k]);//分别假设a[k]之前的符号为“+”、“-” int old=a[k - 1];//若a[k]之前无符号，则要合并，合并之前将旧值储存，方便回溯 char ak[1024] = {0};char ak2[1024]={0};_itoa(a[k - 1],ak,10);_itoa(a[k],ak2,10);strcat(ak,ak2);a[k - 1] = atoi(ak);memset(p,0,k*2 + 1);strcat(p,s);fk(a,k - 1,p,goal);a[k - 1] = old;
}void main()
{int a[]={1,2,3,4,5,6,7,8,9};fk(a,8,"",110);
}