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 里看到的，作者没去说这题的思路。除了穷举外，还有什么好方法呢 🤔
 |
1
geelaw Jan 21, 2019 via iPhone
这个问题（很直白地）是 subset sum，数字都很小的时候用最常见的那个 dynamic programming。此外还可以用 @ChaoXu 之前的研究结果。
该问题是 NP-hard，所以不要期待一个多项式时间的算法。 |
 |
3
guyeu Jan 21, 2019
emmmm 这个问题比 subset sum 多了个限定条件，感觉用二叉树+剪枝可以试试。
|
 |
5
qinyusen Jan 21, 2019
|
 |
7
aijam Jan 22, 2019
|
Select Language