程序填空题：1-9数字间插入加减号计算结果为100问题（回溯法）

设计一个算法在1、2、...、9（顺序不能变）数字之间插入+或-或什么都不插入，使得计算结果总是100的程序，并输出所有的可能性。
### 输出格式:
逐行输出每个解
### 输出样例1:
```out
1+2+3-4+5+6+78+9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12+3-4+5+67+8+9=100
12-3-4+5-6+7+89=100
123+4-5+67-89=100
123+45-67+8-9=100
123-4-5-6-7+8-9=100
123-45-67+89=100
```

```c++
#include
#define N 9
void fun(char op[],int sum,int prevadd,int a[],int i)
{
if () //扫描完所有位置
{
if () //找到一个解
{
printf("%d",a[0]); //输出解
for (int j=1;j {
if (op[j]!=' ')
printf("%c",op[j]);
printf("%d",a[j]);
}
printf("=100\n");
}
return;
}
op[i]='+'; //位置i插入'+'
sum+=a[i]; //计算结果
fun(); //继续处理下一个位置
; //回溯

op[i]='-'; //位置i插入'-'
sum-=a[i]; //计算结果
fun(); //继续处理下一个位置
; //回溯

op[i]=' '; //位置i插入' '
sum-=prevadd; //先减去前面的元素值
int tmp; //计算新元素值
if (prevadd>0)
tmp=prevadd*10+a[i]; //如prevadd=5,a[i]=6,结果为56
else
tmp=prevadd*10-a[i]; //如prevadd=-5,a[i]=6,结果为-56
sum+=tmp; //计算合并结果
fun(); //继续处理下一个位置
sum-=; //回溯sum
sum+=;
}
int main()
{
int a[N];
char op[N]; //op[i]表示在位置i插入运算符
for (int i=0;i a[i]=i+1;
fun(op,a[0],a[0],a,1); //插入位置i从1开始
return 0;
}
```






答案：
第1空：i==N

第2空：sum==100

第3空：op,sum,a[i],a,i+1

第4空：sum-=a[i]

第5空：op,sum,-a[i],a,i+1

第6空：sum+=a[i]

第7空：op,sum,tmp,a,i+1

第8空：tmp

第9空：prevadd