leetcode：494.数组中添加加减运算符得到指定值的所有方法

题目来源

• leetcode：494.数组中添加加减运算符得到指定值的所有方法

题目描述

题目解析

暴力递归

定义：对于数组arr[idx…]中所有的数字，搞出rest这个数，方法是多少。

int process(std::vector<int>&arr, int idx, int rest);

base case：

• 当没有数了，就没有选择了，这个时候看rest是否为0，如果为0，表示找到了一种方法，其他都是没有找到方法

普通情况：

• 就是base case之外的情况，也就是还有数可以选择
• 这个时候，我们要决定对arr[idx]做出选择，做出选择就会对rest造成影响。最后将剩下的递归给arr[idx+1…]

备忘录

对于：

int process(std::vector<int>&arr, int idx, int rest);

只要可变参数idx和rest固定了，那么process的返回值也就固定了

因此，我们只要用一个map指缓存起来，然后如果有，就直接去查就可以，没有就去计算

暴力递归改动态规划

优化

原问题等同于： 找到nums一个正子集P和一个负子集N，使得总和等于target。即
$$sum(P)-sum(N)==target$$

同时有：

$$sum(P)+sum(N)==sum$$

上面两式相加，得到
$$2\ast sum(P)==target+sum(nums)$$

其中target + sum(nums)必须>=0且为偶数，否则等式不可能成立。

则问题转换为：有一些物品，第i个物品的重量为nums[i]， 背包的容量为sum§，问：有多少种方式将背包【恰好填满】