微策略2013年校园招聘笔试题-寻找表达式 | Acm之家

微策略2013年校园招聘笔试题-寻找表达式 | Acm之家

现在有一个序列123……N，其中N介于3和15之间，要求在序列之间加入+、-或者空格，使得该序列组成的数学表达式的运算结果为0。

输入：

输入可能包含多个测试样例。
对于每个测试案例，输入整数N(3<=N<=15)，代表这个序列的长度。

输出：

对应每个测试案例，输出所有使得表达式结果为0的组合，当有多个组合时，按字典序进行排序输出。

样例输入：

3 6

样例输出：

1+2-3 1 2+3-4-5-6

提示：

 1_2+3-4-5-6相当于12+3-4-5-6('_'代表空格)

题目来自九度 1498 http://ac.jobdu.com/problem.php?pid=1498

分析：由于只有 加减两种操作，因此要比普通的 表达式求值简单很多。此题应该算是一个搜索的题目，这里是用的递归(dfs)，穷举所有的情况，符合情况就输出。

是一个练习深搜的不错题目！

在递归的时候分布遍历这3中情况：合并上一个，加，减。

传入参数last，代表上一个数，因为当前数 可以选择和上一个数合并。

比如1_2+3-4-5-6

1就是上一个数，2就是当前数，形成12。

Read full article from 微策略2013年校园招聘笔试题-寻找表达式 | Acm之家