問(wèn)題描述：輸入一個(gè)數(shù)N，給你三個(gè)運(yùn)算符： ，-，空格；空格表示把兩個(gè)數(shù)連起來(lái)比如：“2 3”就等同于23；問(wèn)你有1到N（N < 9）每個(gè)數(shù)之間有一個(gè)運(yùn)算符，要你輸出所有計(jì)算結(jié)果為0的情況。解決方案：我

問(wèn)題描述：

輸入一個(gè)數(shù)N，給你三個(gè)運(yùn)算符： ，-，空格；空格表示把兩個(gè)數(shù)連起來(lái)比如：“2 3”就等同于23；問(wèn)你有1到N（N < 9）每個(gè)數(shù)之間有一個(gè)運(yùn)算符，要你輸出所有計(jì)算結(jié)果為0的情況。

解決方案：

我們可以使用深度優(yōu)先搜索算法進(jìn)行遍歷。首先我們定義一個(gè)sum變量，存儲(chǔ)現(xiàn)有計(jì)算出的值，再定義一個(gè)left記錄掃描到的最后一個(gè)數(shù)的值，step表示掃描到的數(shù)字。遞歸關(guān)系如下圖所示：

![]()

判斷是否滿(mǎn)足條件時(shí)別忘了判斷時(shí)要給sum加left。即sum left0。

代碼實(shí)現(xiàn)：

```c

include

include

include

include

include

using namespace std;

int N;

int dfs(int sum, int step, int left, string print){

if(stepN){

if(sum left 0){

cout << print << endl;

return 0;

}

else

return 0;

}

if(left<0)

dfs(sum,step 1,left*10-step-1,print ' ' (char)(step 1 '0'));

else

dfs(sum,step 1,left*10 step 1,print ' ' char(step 1 '0'));

dfs(sum left,step 1,step 1,print ' ' char(step 1 '0'));

dfs(sum left,step 1,0-step-1,print '-' char(step 1 '0'));

}

int main(){

freopen("","r",stdin);

freopen("zerosum.out","w",stdout);

scanf("%d",N);

dfs(0,1,1,"1");

return 0;

}

```

本人比較懶，在這道題中沒(méi)有使用任何優(yōu)化剪枝，結(jié)果運(yùn)算結(jié)果居然只要0ms！??！估計(jì)usaco出了點(diǎn)小問(wèn)題。