组合运算式

请考虑一个被空格分隔的，由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;
}