题目描述
请考虑一个由1到N（N=3, 4, 5 ... 9）的数字组成的递增数列：1 2 3 ... N。现在请在数列中插入“+”表示加，或者“-”表示减，抑或是“ ”表示空白，来将每一对数字组合在一起（请不在第一个数字前插入符号）。计算该表达式的结果并注意你是否得到了和为零。请你写一个程序找出所有产生和为零的长度为N的数列。
INPUT FORMAT
单独的一行表示整数N (3 <= N <= 9)。
SAMPLE INPUT (file zerosum.in)
7
OUTPUT FORMAT
按照ASCII码的顺序，输出所有在每对数字间插入“+”, “-”, 或 “ ”后能得到和为零的数列。(注意:就算两个数字之间没有插入符号也应该保留空格)
SAMPLE OUTPUT (file zerosum.out)
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
这道题目一看就知道是搜索，可是搜完之后应该如何计算这个式子的值呢？
因为这里多了一个' '，所以我们就需考虑这个，然而这个应该是优先的，意思就是说要先算这一个.当我们用b数组来存每个数时，一个数的左边以及右边都不为' '，才不是“优先”的，就可以记录下来了，然后再记录空格的sum，最后用ans来存储答案。
代码：
var
n,i,sum,ans,w:Longint;
a:array[0..9] of char;
b:array[1..9] of longint;
procedure print;
begin
for i:=1 to n-1 do
write(i,a[i]);
writeln(n);
end;
procedure dfs(k:Longint);
begin
if k=n then
begin
fillchar(b,sizeof(b),0);
for i:=1 to n do
if (a[i]<>' ') and (a[i-1]<>' ') then b[i]:=i;
sum:=1;
w:=0;
for i:=1 to n do
if a[i]=' ' then
begin
sum:=sum*10+i+1;
if w=0 then w:=i;
end
else
begin
if w<>0 then
begin
b[w]:=sum;
w:=0;
end;
sum:=i+1;
end;
ans:=b[1];
for i:=1 to n-1 do
begin
if a[i]='+' then ans:=ans+b[i+1];
if a[i]='-' then ans:=ans-b[i+1];
end;
if ans=0 then print;
exit;
end;
a[k]:=' ';
dfs(k+1);
a[k]:='+';
dfs(k+1);;
a[k]:='-';
dfs(k+1);
end;
begin
readln(n);
dfs(1);
end.
当然，这道题也有别的方法，我们可以考虑不在全部枚举完之后再计算值，可以边枚举边算：
sum表示当前总和，rest表示的是当前连数的和。（这里需要注意，rest的和不止是代表当前连续数字的和，当没有' '的时候，rest也会代表着下一个要加减的数，这样可以方便sum计算）如果是' '就只需更新rest,否则如果是加的话，先加上rest,因为rest如果是负数，加上一个负数也是一样的，然后在＋，－的时候判断rest是往正数还是负数更新（这个地方是重点，也是简便之处）（另外递归符号的顺序一定得是' ','+','-'，题目输出顺序）
var
n,i:LOngint;
a:array[1..9] of char;
Procedure print;
begin
for i:=1 to n-1 do
write(i,a[i]);
writeln(n);
end;
Procedure dfs(sum,rest,k:Longint);
begin
if k=n then
begin
if sum+rest=0 then print;
exit;
end;
a[k]:=' ';
if rest<0 then
dfs(sum,rest*10-k-1,k+1)
else
dfs(sum,rest*10+k+1,k+1);
a[k]:='+';
dfs(sum+rest,k+1,k+1);;
a[k]:='-';
dfs(sum+rest,-(k+1),k+1);
end;
begin
readln(n);
dfs(0,1,1);
end.