数据结构与算法之叛徒定理@慕课网原创_慕课网

Problem
    在多个数字之间填入 + 或 -  使等式成立！
    输入：
            n-----需要参与计算的数字个数
            result-----经过计算得出的结果
    输出：
            若能填出，则输出只含有加减运算的完整的表达式，若不能则输出NO。

Simple Input
6
1 2 3 4 5 6
11
6
1 2 3 4 5 6
10

Simple Output
1 + 2 + 3 + 4 - 5 + 6 = 11
1 - 2 - 3 + 4 + 5 + 6 = 11
NO

Hint
首位前不能有符号。

首先提出这样的一个问题

1 2 3 4 5 6 = 11，在数字之间填入+ 或- 使等式成立！

此时引入——叛徒定理！！！

何为叛徒定理？在一个王国中，有平民也有叛徒，此时为每一个人（指定国王为1号）进行编号，国王（不能是叛徒）的任务就是找到叛徒。判断谁是叛徒，只需要把总数里减少的部分除以二，就可以确定。

1 + 2 +3 + 4 + 5 + 6 = 21
1 2 3 4 5 6 = 11
21 - 11 = 10
10 / 2 = 5

所以 5 是这个王国里的叛徒，然而没有说明到底有几个叛徒，所有能成为 5 的组合（2+3）也需考虑在内。
1.编号为 5 位叛徒 1 + 2 + 3 + 4 - 5 + 6 = 11
2.编号为 2 和 3 为叛徒 1 - 2 - 3 + 4 +5 + 6 = 11

将这种思想广义化，任意填写数字，判断是否能够找到使等式成立的表达式。

如： 3  5  8  4  20  14= 14
     3 + 5 + 8 + 4 - 20 + 14 = 14