请教一道算法题

[lcj2class]

Given an array with positive integers and another integer for example {7 2 4} and 9, you are required to generate an equation, by inserting operator add ("+") and minus ("-") among the array. The left side of equation are consist of the array and the right side of equation is the integer. Here the result is 7-2+4=9.

无意间在 http://www.raychase.net/1285 里看到的，作者没去说这题的思路。除了穷举外，还有什么好方法呢 🤔

[geelaw]

这个问题（很直白地）是 subset sum，数字都很小的时候用最常见的那个 dynamic programming。此外还可以用 @ChaoXu 之前的研究结果。

该问题是 NP-hard，所以不要期待一个多项式时间的算法。

[enenaaa]

@geelaw 请教下为啥数字大的时候不能用动态规划

[guyeu]

emmmm 这个问题比 subset sum 多了个限定条件，感觉用二叉树+剪枝可以试试。

[geelaw]

@enenaaa #2 数字大的时候动态规划不如枚举有效率

[qinyusen]

@geelaw https://blog.csdn.net/john548/article/details/52217143

[qinyusen]

@geelaw 额，刚才 at 错人了。。。

[aijam]

backtrack
https://gist.github.com/czheo/b244f443c3ecbab88aa2ddea192db90f

[lcj2class]

@geelaw #4 是说数字大的时候会有额外的 overhead，有没有相关文章介绍的呢？

[geelaw]

@lcj2class 举个例子，有 n 个数，最大的数大小是 3^n，则 DP 的时间复杂度是 Omega(3^n) 但枚举的时间复杂度是 O(2^n*poly(n))。

如果你用“刷新式”实现动态规划则另谈。