今天百无聊赖之时， 漫心看到14年的华为校招机试题目， 一共三道， 前两道皆是平平， 第三道却柳暗花明， 让人眼前一亮。 咋一看， 饶有趣味， 看似平淡无奇， 然而却玄机颇深（对我这种弱渣而言）。（不过对于ACMer， 好像应该用基础算法， 就能解决！）
（然而我也只会基础的算法！！忏愧的紧！！！）。如果有幸被大神看到， 能指点我一两招， 不胜感激！ 下面是题目和我的详细题解思路（可供巨巨一笑！嘿嘿！）。
2014年七月华为校招机试题目：
第三题：
输入一个正整数X，在下面的等式左边的数字之间添加+号或者-号，使得等式成立。
1 2 3 4 5 6 7 8 9 = X
比如：
12-34+5-67+89 = 5
1+23+4-5+6-7-8-9 = 5
请编写程序，统计满足输入整数的所有整数个数。
输入： 正整数，等式右边的数字
输出： 使该等式成立的个数
样例输入：5
样例输出：21
看似好复杂的题目 ~~~
稍微冷静的思考一下：
这道题看似复杂， 但是作为校招题应该不会太难。 所以， 冷静的思考一下， 能否对这个问题进行建模？ 稍微了解一点算法的都应该知道： 一切的算法问题都不过是搜索问题。 所以只要建立一个正确的搜索模型就行了。 而搜索模型的建立， 主要是明确状态是如何转换的。
稍微用几个脑细胞就会发现，在这道题中， 状态只有三种转化方式， +， -，*10+。 例如： 1 要转化为下一个状态， 无非是 1+2； 1-2； 1*10+2=12 三种状态而已。 这样解决方案就立刻明朗了， 无非就是从状态 1 依次搜索到状态 9 而已，求方案数用DFS搜索一遍就行了啊。 但是，这个题还有一点小坑的地方： 例如DFS某条搜索路径是： 12-34+5-67+89， 你如果直接计算，得到的结果是这样的： 1*10+2=12， 12-3=9，9*10+4 = 94（正确结果应该是 12-34 = -22 ,,,）， ，，， 咿呀呀。所以是不能直接算的， 解决方案是可以把搜索的路径保存下来。问题很明确了： DFS求能到达某一点的所有路径。
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 using namespace std; 5 6 // 字符串式子求和： 例如 "12-34+5-67+89" 7 int getSum(const string& str) 8 { 9 int ans = 0, num = 0; 10 int i; 11 while(str[i] >= '1' && str[i] <= '9') 12 { 13 ans = ans * 10 + str[i] - '0'; 14 i++; 15 } 16 while(i < str.size()) 17 { 18 19 char op = str[i]; 20 i++; 21 num = 0; 22 while(str[i] >= '1' && str[i] <= '9') 23 { 24 num = num * 10 + str[i] - '0'; 25 i++; 26 } 27 if(op == '+') 28 ans += num; 29 else if(op == '-') 30 ans -= num; 31 } 32 33 return ans; 34 } 35 36 // DFS 求方案数 37 void dfs(const int target, int pos, string str, int &cnt) 38 { 39 if(pos == 10) 40 { 41 if(getSum(str)== target) 42 cnt++; 43 return; 44 } 45 46 dfs(target, pos+1, (str + "+").append(1, pos+'0'), cnt); 47 dfs(target, pos+1, (str + "-").append(1, pos+'0'), cnt); 48 dfs(target, pos+1, str.append(1, pos + '0'), cnt); 49 50 } 51 52 int main() 53 { 54 int n; 55 while(scanf("%d", &n) != EOF) 56 { 57 int cnt = 0; 58 string str="1"; 59 dfs(n, 2, str, cnt); 60 printf("%d ", cnt); 61 } 62 return 0; 63 }