简单的回溯题。考点可能在于表达式的求值吧。
由于' '操作符的优先级大于+,-，可以用一个栈来实现表达式求值。
不过比较麻烦。
这里通过保存last_op，如果当前的操作符是' '的话，则last_op不变，直到遇到新的+/-操作符。
然后开始计算。
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("zerosum.in");
ofstream out("zerosum.out");
// express保存回溯产生的操作符序列
char express[10];
void backtraing(int depth);
int compute_express();
int n;
static int cnt = 0;
void solve()
{
in>>n;
backtraing(0);
}
void backtraing(int depth)
{
if(depth==n-1){
int res = compute_express();
if(res==0){
for(int i=1;i<n;++i)
out<<i<<express[i-1];
out<<n<<endl;
}
return ;
}
express[depth]=' ';
backtraing(depth+1);
express[depth]='+';
backtraing(depth+1);
express[depth]='-';
backtraing(depth+1);
}
//计算表达式的值
int compute_express()
{
char last_op = '+';
int res = 0;
int operand = 1;
for(int i=0;i<n-1;++i){
if(express[i]==' '){
operand = operand*10+i+2;
}else {
if(last_op=='+')
res+=operand;
else
if(last_op=='-')
res-=operand;
operand=i+2;
last_op = express[i];
}
}
if(last_op=='+')
res+=operand;
if(last_op=='-')
res-=operand;
return res;
}
int main(int argc,char *argv[])
{
solve();
return 0;
}