題目：494. 目標和

思路

01背包

轉換為01背包問題

難點在于看出可以用背包問題解決本題；
題目字面意思是劃分出一堆再減去另一堆，得到的結果想要等于target，設定一堆為正，記為left，另一堆為負，記為right，所有數的和為sum。
有left + right = sum，left - right = target，解得left = (target + sum) / 2，right = (sum - target) / 2，因為left是一個整數，所以target + sum必須為偶數，同時right為正數，所以sum - target也必須為正；

01背包

• f[j] ：區間[0, i]的數字放進容積為j的背包里，有f[j]這么多種放法；
• $f[j]={\sum }_{i=0}^{i}f[j?nums[i]]$，在保證j - nums[i]有效性的前提下，這是一個組合問題，相當于在前面一個的基礎上選nums[0]，或者選nums[1]，… … 或者選nums[i]，最后把這些情況都加起來；
• f[0] = 0；
• weights[i] = nums[i]，values[i] = nums[i]

代碼

// 01背包
// f[j] : [0, i]這個區間的數放進容量為j的背包里，有幾種方法
// f[j] = sum(f[j - nums[i]])
// weights[i] = nums[i], values[i] = nums[i];
// f[0] = 1
// 注意 target 有可能為負數
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int i, j;int size = nums.size(), sum = 0;int f[1005] = {0};f[0] = 1;for(i = 0; i < size; i++){sum += nums[i];}cout << "sum : " << sum;// 不合法if((target + sum) % 2 == 1 || sum < abs(target)){return 0;}for(i = 0; i < size; i++){for(j = sum; j >= nums[i]; j--){f[j] += f[j - nums[i]];}}return f[(sum + target)/2];}
};