转化成为背包dp问题,一个数字可以选择 + or -
ref{:target=_blank}
C++ 代码
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int offset = 1000;
if(abs(target) > offset) return 0;
int n = nums.size();
// 用f[i][j]表示前i个数,总和为j的所有方案
vector<vector<int>> f(n+1, vector<int>(2*offset+1));
f[0][offset] = 1;
for(int i=1; i<=n; ++i) {
for(int j=-1000; j<=1000; ++j) {
int num = nums[i-1];
// if条件防止越界
// num 取正数
if(j-num+offset>=0)f[i][j+offset] += f[i-1][j-num+offset];
// num 取负数
if(j+num+offset<=2*offset)f[i][j+offset] += f[i-1][j+num+offset];
}
}
return f[n][target+offset];
}
};