遍历上花费了好长时间....
题面：
仍然是dfs+回溯。需要注意的是ascii码表上的顺序：‘ ’‘+’‘-’，可以建立两个char数组，一个存储0-9所有数字，另一个存储所用到的符号。当所用的符号个数为n-1时进行检查。我在遍历上出了点问题，样例一直没有过。主要是空格如何进行读取。思考了很久想到了倒序遍历，因为加减号并不影响运算的顺序，所以可以进行倒序遍历，当出现空格时处理带有空格的全部数字，然后再进行加减即可。代码如下：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int n,sum=0; 5 char num[10]={‘0‘,‘1‘,‘2‘,‘3‘,‘4‘,‘5‘,‘6‘,‘7‘,‘8‘,‘9‘},ans[11]; 6 void dfs() 7 { 8 if (sum==n) 9 { 10 int fsum=0; 11 for (int i=n;i>=0;i--)//倒序遍历 12 { 13 if (ans[i]==‘ ‘) 14 { 15 int q=10,nsum=num[i+1]-‘0‘; 16 while (ans[i]==‘ ‘&&i>=1)//对空格处的数进行特殊处理 17 { 18 nsum+=(num[i]-‘0‘)*q; 19 q*=10; 20 i--; 21 } 22 if (ans[i]==‘+‘) 23 fsum+=nsum; 24 else 25 fsum-=nsum; 26 } 27 else if (ans[i]==‘+‘) 28 fsum+=num[i+1]-‘0‘; 29 else 30 fsum-=num[i+1]-‘0‘; 31 } 32 if (fsum==0) 33 { 34 for (int i=1;i<=n;i++) 35 printf("%c%c",num[i],ans[i]); 36 printf("%c\n",num[n+1]); 37 } 38 } 39 else 40 for (int i=1;i<=3;i++) 41 { 42 sum++; 43 if (i==1) 44 ans[sum]=‘ ‘; 45 else if (i==2) 46 ans[sum]=‘+‘; 47 else 48 ans[sum]=‘-‘; 49 dfs(); 50 sum--; 51 } 52 } 53 int main() 54 { 55 //freopen("add.in","r",stdin); 56 //freopen("add.out","w",stdout); 57 ans[0]=‘+‘;//第一个数字的前方一定是正号 58 scanf("%d",&n); 59 n--; 60 dfs(); 61 return 0; 62 }
原文：http://www.cnblogs.com/hinanawitenshi/p/6398502.html
