494. 目標和

給你一個非負整數數組 nums 和一個整數 target 。
向數組中的每個整數前添加 ‘+’ 或 ‘-’ ，然后串聯起所有整數，可以構造一個 表達式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串聯起來得到表達式 “+2-1” 。
返回可以通過上述方法構造的、運算結果等于 target 的不同 表達式 的數目。
示例 1：
輸入：nums = [1,1,1,1,1], target = 3
輸出：5
解釋：一共有 5 種方法讓最終目標和為 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
輸入：nums = [1], target = 1
輸出：1
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

---

題解

首先對題目進行分析
所有的數字都要選，我們能做的是決定數字前面的符號，也就是這個數字是 + 還是 -
那么不妨將最后的結果視為 p - a，p為正數之和，a為負數之和，我們能夠通過選擇數字決定 p 是多少
又因為 p - a = target，a = sum（所有數的絕對值之和）- p，所以 p = (target + sum)/2
題目就變成從數組 nums 中選擇數字使其和為 (target + sum)/2 （不能重復選擇） ，這樣就是01背包問題了

由于 p 是非負整數，所以如果target + sum是奇數或者負數，那么答案肯定是 0

定義 arr[ i ][ j ] 為選擇前 i 個數使其和為 j 的方法數
那么對于任意 arr[ i ][ j ] ，只有選擇 nums[ i-1 ] 和不選擇兩種可能
如果 nums[ i-1 ]>j，只能不選，arr[ i ][ j ]=arr[ i-1 ][ j ]
否則，arr[ i ][ j ]=arr[ i-1 ][ j ] + arr[ i-1 ][ j-nums[ i-1] ]
初始化 arr[0][0]=1，其余arr[0][j]為0
按順序遍歷數組即可

---

代碼如下↓

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// p p是我們選擇的正數// s-p s是所有正數的和// 2p-s=target// p=(target+s)/2// 那么就是選擇數使其和為 p 即可int n=nums.size();int s=0;for(int i=0;i<n;i++){s+=nums[i];}if((target+s)%2 || target+s<0){return 0;}int p=(target+s)/2;vector<vector<int>> arr(n+1,vector<int>(p+1,0));arr[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=p;j++){arr[i][j]=arr[i-1][j];if(nums[i-1]<=j){arr[i][j]+=arr[i-1][j-nums[i-1]];}}}return arr[n][p];}
};

---

優化空間

二維滾動數組

我們發現 arr[ i ][ j ]=arr[ i-1 ][ j ] + arr[ i-1 ][ j-nums[ i-1] ] 或 arr[ i ][ j ]=arr[ i-1 ][ j ]
arr[ i ][ j ] 僅與上一行的 arr 有關，那我們不妨將二維數組縮減至兩行，一行存 i-1 ，一行存 i
在執行過程中進行滾動，將 i 和 i-1變為 i%2 和 (i-1)%2，從而優化空間

---

代碼如下↓

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// p p是我們選擇的正數// s-p s是所有正數的和// 2p-s=target// p=(target+s)/2// 那么就是選擇數使其和為 p 即可int n=nums.size();int s=0;for(int i=0;i<n;i++){s+=nums[i];}if((target+s)%2 || target+s<0){return 0;}int p=(target+s)/2;vector<vector<int>> arr(2,vector<int>(p+1,0));arr[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<=p;j++){arr[i%2][j]=arr[(i-1)%2][j];if(nums[i-1]<=j){arr[i%2][j]+=arr[(i-1)%2][j-nums[i-1]];}}}return arr[n%2][p];}
};

---

一維數組

類似的，既然arr[ i ][ j ] 僅與上一行的 arr 有關，一行，我們能否用一位數組表示

arr[ j ] = arr[ j ] + arr[ j-nums[ i-1 ] ]（前面的arr[ j ]是arr[ i ][ j ]，后面的都是arr[ i-1 ][ j ]，上一行的）

同時，我們發現 arr[ j+1 ] 與其上一行的前面的數據有關
如果我們從前往后進行遍歷，那么后面的 arr[ j+1 ] 需要的 arr[ j ] 的數據就被新計算出來的 arr[ j+1 ] 給覆蓋了
所以我們需要從后向前遍歷，這樣就不會發生需要的數據被覆蓋的問題了

---

代碼如下↓

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {// p p是我們選擇的正數// s-p s是所有正數的和// 2p-s=target// p=(target+s)/2// 那么就是選擇數使其和為 p 即可int n=nums.size();int s=0;for(int i=0;i<n;i++){s+=nums[i];}if((target+s)%2 || target+s<0){return 0;}int p=(target+s)/2;vector<int> arr(p+1);arr[0]=1;for(int i=1;i<=n;i++){for(int j=p;j>=0;j--){if(nums[i-1]<=j){arr[j]+=arr[j-nums[i-1]];}}}return arr[p];}
};