Python使用超高效算法查找所有类似123-45-67+89=100的组合

问题描述：在123456789这9个数字中间插入任意多个+和-的组合，使得表达式的值为100，输出所有符合条件的表达式。

前面发了一个暴力测试的方法来解决问题，详见Python查找所有类似于123-45-67+89 = 100的组合，但是暴力测试的方法非常慢，大概需要运行3个小时多。今天分享一个超高效的算法及其实现，可以瞬间输出所有结果，感谢中国传媒大学胡凤国老师提供这个神奇的算法。

主要思路：设计一个三进制加法算法，让8个0逐步变化到8个3，其中每一位上的数字可以是0、1、2，然后让0对应空格、1对应+、2对应-，然后在1到9之间的8个位置上分别插入空格、+或-符号，最后删掉表达式中的空格并求值，如果等于100则满足条件。

参考代码：

运行结果：