请考虑一个被空格分隔的，由1到N的整数组成的递增数列：1 2 3 ... N。现在请在数列中插入表示加的“+”，或者表示减“-”，亦或者表示空白的“ ”(例如1-2 3就等于1-23)，来将每一对数字组合成一个表达式（第一个数字前无空格）。计算该表达式的结果并判断其值是否为0。请你写一个程序找出所有产生和为零的长度为N的数列。
输入为一行，包含一个整数N（3≤N≤9）。
输出为所有在每对数字间插入“+”, “-”, 或 “ ”后能得到和为零的数列，并按照字典（ASCII码）序排列。
样例输入
7
样例输出
1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7
难度：3
考察：DFS
#include <cstdio>
using namespace std;
const int MAX_N = 11;
int num[MAX_N],result[MAX_N];
int ope[MAX_N];
int N;
bool start=false;
//取一个整数的最高位数字
int get_order(int x){
while(x>=10)
{
x = (x - (x % 10)) / 10;
}
return x;
}
//运算，0，1，-1分别代表" "，"+"，"-"
int operation(int a,int b,int ope){
if(ope==0){
return a*10+b;
}
else if(ope==1){
return a+b;
}
else return a-b;
}
void updateResult(int i,int p){
ope[i-1]=p;//ope数组记录当前所用的运算符
if(p==0){
int index = get_order(num[i-1]);
result[i] = result[index-1];//回到没有对上一个数字运算前的结果
int ope1 = ope[index-1];
num[i] = operation(num[i-1],i,0);//当前参与运算的数字
result[i] = operation(result[i],num[i],ope1);
}
else{
num[i]=i;
result[i] = operation(result[i-1],num[i],p);
}
}
void show_f(){
if(start){
printf("\n");
}
for (int i = 1; i <=N; ++i) {
printf("%d",i);
if(i> N-1)break;
if(ope[i]==-1)printf("-");
else if(ope[i]==0)printf(" ");
else printf("+");
}
start = true;
}
void dfs(int i){
if(i>N){
if(result[i-1]==0)show_f();
return;
}
updateResult(i,0);
dfs(i+1);
updateResult(i,1);
dfs(i+1);
updateResult(i,-1);
dfs(i+1);
}
int main() {
scanf("%d",&N);
num[1]=1;//num数组记录参与运算的数字
result[0]=0;//result数组表示当前结果
result[1]=1;
dfs(2);
return 0;
}
