描述
有一个未完成的等式：1 2 3 4 5 6 7 8 9=N。
题目
给出整数N的具体值后，请你在2，3，4，5，6，7，8，9这8个数字的每一个前面，或插入一个运算符号“+”号，或插入一个运算符号“-”号，或不插入任何运算符号，使等式成立，并统计出能使等式成立的算式总数，若无解，则输出0。例如：取N为108时，共能写出15个不同的等式，以下就是其中的二个算式：
1+23+4+56+7+8+9=108
123-45+6+7+8+9=108
输入
只有1个数，即整数N的值。-30000≤n≤1000000
输出
只有一行，该行只有1个数，表示能使等式成立的算式总数。
输入样例1
108
输出样例1
15
解题思路
此题先DFS搜一遍从2到9每个数字前的符号情况，用数组存起来，最后在求值即可。
题解
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,ans=0; 4 bool flag; 5 int num[11];//0没有，1加法，2减法 6 void dfs(int sum) 7 { 8 if(sum==10)//所有的枚举完了 9 { 10 int q=0,p=0;//q是总值，p是变量值 11 for(int i=1;i<=9;)//九个数字 12 { 13 if(num[i]==1)flag=true;//true就是加，false是减 14 if(num[i]==2)flag=false; 15 p=i;//首先存入这个数 再来看他后面的符号 16 i++; 17 while(num[i]==0&&i<=9)//判断数字连着的情况，*10+数字即可 18 { 19 p=p*10+i; 20 i++; 21 } 22 if(flag)//加法就加 23 { 24 q+=p; 25 } 26 else q-=p;//减法就减 27 } 28 if(q==n)ans++; //值是正确的方案加一 29 return; 30 } 31 num[sum]=0;//搜索三种符号情况 32 dfs(sum+1); 33 num[sum]=1; 34 dfs(sum+1); 35 num[sum]=2; 36 dfs(sum+1); 37 } 38 int main() 39 { 40 cin>>n; 41 num[1]=1;//1前面一定是加，不要忘了 42 dfs(2);//从第二位前面开始 43 cout<<ans; 44 return 0; 45 }
借鉴专用区（大家都懂）
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,ans=0; 4 bool flag; 5 int num[11]; 6 void dfs(int sum) 7 { 8 if(sum==10) 9 { 10 int q=0,p=0; 11 for(int i=1;i<=9;) 12 { 13 if(num[i]==1)flag=true; 14 if(num[i]==2)flag=false; 15 p=i; 16 i++; 17 while(num[i]==0&&i<=9) 18 { 19 p=p*10+i; 20 i++; 21 } 22 if(flag) 23 { 24 q+=p; 25 } 26 else q-=p; 27 } 28 if(q==n)ans++; 29 return; 30 } 31 num[sum]=0; 32 dfs(sum+1); 33 num[sum]=1; 34 dfs(sum+1); 35 num[sum]=2; 36 dfs(sum+1); 37 } 38 int main() 39 { 40 cin>>n; 41 num[1]=1; 42 dfs(2); 43 cout<<ans; 44 return 0; 45 }