簡(jiǎn)單的回溯題?？键c(diǎn)可能在于表達(dá)式的求值吧。
由于' '操作符的優(yōu)先級(jí)大于+,-，可以用一個(gè)棧來實(shí)現(xiàn)表達(dá)式求值。
不過比較麻煩。
這里通過保存last_op，如果當(dāng)前的操作符是' '的話，則last_op不變，直到遇到新的+/-操作符。
然后開始計(jì)算。
#include?<iostream>
#include?<fstream>
using?namespace?std;
ifstream?in("zerosum.in");
ofstream?out("zerosum.out");
// express保存回溯產(chǎn)生的操作符序列
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);
}
//計(jì)算表達(dá)式的值
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;
}