如何优化仅单次使用给定数字构造目标值的数字游戏编码？

你当前的实现之所以计算慢，核心是穷举过程中生成了太多重复、等价、甚至根本不合法的表达式，以下优化可以直接把耗时从20秒级压到毫秒级。

核心枚举逻辑替换（最大性能提升来源） #

不要再把数字、运算符拼在一起做全排列枚举，换为按子集大小逐层分治的动态规划逻辑：

• 为每个非空输入子集建一个结果映射表，记录这个子集通过合法四则运算能得到的所有去重结果
• 从最小的子集开始计算：先把所有长度为2的子集的合法运算结果（加减乘除，排除非法的除零、非必要的非整数结果）存入映射表
• 对长度k>2的子集，把它拆成两个互不重叠的非空真子集A、B，遍历A和B的所有结果，两两做合法四则运算，把结果去重后存入当前子集的结果表
  这套逻辑和原全排列逻辑比，最大的优势是完全复用重复计算：比如[2,5]和[5,2]本质是同一个子集，只需要算一次能得到7、3、10这些结果，后续所有用到这个组合的表达式直接拿结果复用就行，不用反复对数字做全排列、反复算2+5和5+2这种完全一样的结果，通常这一步就能砍掉90%以上的无效计算。

剪枝规则强化 #

在枚举过程中碰到明显不可能凑出目标的分支，直接砍掉，不要硬算到底：

• 对每个子集先算两个边界值：理论最大值（所有正整数直接相乘的结果）、理论最小值（所有数直接相加的结果）。如果最大值都比目标小，或者最小值都比目标大，直接把这个子集从枚举列表删掉，连DP计算都不用跑
• 两两做运算的时候提前判断可达性：比如两个子集乘出来的结果远大于目标值，剩下没用到的数的总和都不够把这个结果减到目标范围里，直接把这个结果丢掉，不用存进结果表
• 运算结果去重：所有满足交换律的等价结果（a+b和b+a、a*b和b*a）只存一次，除不尽的非整数结果（如果题目要求整数输出）直接过滤，这部分能再砍掉30%-50%的计算量

原有优化的升级 #

你之前做的“子集总和小于目标就过滤不含乘法的运算符排列”是有效的，但可以进一步升级：

• 生成运算符排列的时候，跳过带重复元素的排列。比如三个运算符位置里有两个加号，不管这两个加号怎么换位置，结果都是完全等价的，没必要反复生成验证，这部分能砍掉一半以上的无意义排列数
• 不要等所有运算符排列生成完再过滤，提前在子集校验阶段就标记不可能的组合，省得后续循环浪费时间

遍历顺序优化 #

把原来按子集任意顺序遍历的逻辑，改成按子集长度从小到大遍历（先算2个元素的子集，再算3个、4个元素的）。因为凑出目标值通常只需要用到少量数字（比如你举的例子只用4个数字就凑出了280），一旦在某个长度的子集里算出目标值，直接返回结果就行，根本不需要继续遍历更长的、复杂度高得多的子集。如果原来的遍历顺序是从最长的子集开始算，哪怕短子集有解，也要先把所有长子集跑一遍，会浪费巨量时间。

减少无效转换开销 #

你原来的逻辑是对“数字+运算符”的混合序列做全排列，这里面大部分序列根本不是合法的表达式结构（比如开头是运算符、操作数数量永远少于运算符数量），你转换为后缀表达式算结果的时候还要反复校验合法性，这部分开销完全可以省掉：分治DP生成的表达式天生就是合法结构，不需要做合法性校验，直接在算结果的时候记录对应的表达式字符串就行。你当前用到的Heap全排列、postfixToInfix转换环节，在新逻辑下大部分都不需要运行。

实际落地效果参考：同样7个输入数字凑280目标值的场景，用上以上优化的实现通常耗时在10毫秒以内，和你当前20秒级的耗时相比是数量级的提升。

内容的提问来源于stack exchange，提问作者vignerd