题目描述
给定一个由 1∼N 构成的序列:1,2,…,N。
现在,你要在序列的数字与数字之间插入一些符号,插入+表示加法运算,插入-表示减法运输,插入(空格)表示数字合并为一个数。
在全部插入完毕后,将得到一个可以看作表达式的新序列。
计算该表达式的结果,看看结果是否为 0。
现在,请你编写一个程序,给定整数 N,找到并输出所有的长度为 N 且总和为零的序列。
输入样例
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
C++ 代码
#include <iostream>
using namespace std;
const int N = 10;
// oprea[i] 存储数i与i+1之间的操作
// 存储1表示"+",2表示"-",3表示" "
int n, oprea[N];
// 得到第t次操作下的数值
// 如果oprea[t]为3则开始合并操作, 直至遇到下一次操作不为3
int get_num(int t){
int tmp = t;
while(oprea[t] == 3){
tmp = 10 * tmp + t + 1;
t ++;
}
return tmp;
}
void print(){
printf("1");
for(int i = 1; i < n; i ++){
if(oprea[i] == 1)
printf("+");
else if(oprea[i] == 2)
printf("-");
else
printf(" ");
printf("%d", i + 1);
}
puts("");
}
void dfs(int x){
// 设置递归出口
if(x == n){
// s定义为前i项和, 初始s = a[1] = get_num(1);
int s = get_num(1);
for(int i = 1; i < n; i ++)
if(oprea[i] == 1)
// 得到需要加的数
s += get_num(i + 1);
else if(oprea[i] == 2)
// 得到需要减的数
s -= get_num(i + 1);
if(s == 0) print();
return;
}
// 按字典序输出, 则以" "."+"."-"的顺序进行dfs
oprea[x] = 3;
dfs(x + 1);
// 因为顺序执行,恢复现场会被二次覆盖,所以无需显示化恢复现场的过程
// oprea[x] = 0;
oprea[x] = 1;
dfs(x + 1);
// oprea[x] = 0;
oprea[x] = 2;
dfs(x + 1);
// oprea[x] = 0;
}
int main(void){
scanf("%d", &n);
// 从第一个操作数开始dfs
dfs(1);
return 0;
}