给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 

思路1：DFS

DFS真是百搭，但是也总是耗时过长

思路2：trick

同完全平方和那道题一样，又用到了个数学上的trick。

这道题等价于找一个正数集P，一个负数集N，使得sum(P) - sum(N) = S。

注意到 sum(P) + sum(N)  = sum，且 sum + S = 2*sum(P) 或 sum - S = 2*sum(N)

所以只需要在非负整数组里找一个子集，满足其和等于 (sum + S)/2 或  (sum - S)/2。

接下来的问题是，怎么找这个子集：选或不选，当然是0-1背包啦。 

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄