494. 目標和

題目連結：https://leetcode-cn.com/problems/target-sum/

難度：中等

給定一個非負整數陣列，a1, a2, ..., an, 和一個目標數，S。現在你有兩個符號 + 和 -。對於陣列中的任意一個整數，你都可以從 + 或 -中選擇一個符號新增在前面。

返回可以使最終陣列和為目標數 S 的所有新增符號的方法數。

示例：

輸入：nums: [1, 1, 1, 1, 1], S: 3 輸出：5 解釋：

-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

一共有5種方法讓最終目標和為3。

提示：

事實確實如此，下面我也會給出相應的程式碼，只不過會超時，哈哈。

這道題目咋眼一看和動態規劃揹包啥的也沒啥關係。

本題要如何使表示式結果為target，

既然為target，那麼就一定有 left組合 - right組合 = target。

left + right等於sum，而sum是固定的。

公式來了， left - (sum - left) = target -> left = (target + sum)/2 。

target是固定的，sum是固定的，left就可以求出來。

此時問題就是在集合nums中找出和為left的組合。

此時可以套組合總和的回溯法程式碼，幾乎不用改動。

當然，也可以轉變成序列區間選+ 或者 -，使用回溯法，那就是另一個解法。

但無論哪種回溯法，時間複雜度都是是O(2^n)級別，所以最後超時了。

我也把程式碼給出來吧，大家可以瞭解一下，回溯的解法，以下是本題轉變為組合總和問題的回溯法程式碼：

class Solution {private:    vector<vector<int>> result;    vector<int> path;    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {        if (sum == target) {            result.push_back(path);        }        // 如果 sum + candidates[i] > target 就終止遍歷        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {            sum += candidates[i];            path.push_back(candidates[i]);            backtracking(candidates, target, sum, i + 1);            sum -= candidates[i];            path.pop_back();        }    }public:    int findTargetSumWays(vector<int>& nums, int S) {        int sum = 0;        for (int i = 0; i < nums.size(); i++) sum += nums[i];        if (S > sum) return 0; // 此時沒有方案        if ((S + sum) % 2) return 0; // 此時沒有方案，兩個int相加的時候要各位小心數值溢位的問題        int bagSize = (S + sum) / 2; // 轉變為組合總和問題，bagsize就是要求的和        // 以下為回溯法程式碼        result.clear();        path.clear();        sort(nums.begin(), nums.end()); // 需要排序        backtracking(nums, bagSize, 0, 0);        return result.size();    }};

動態規劃

如何轉化為01揹包問題呢。

假設加法的總和為x，那麼減法對應的總和就是sum - x。

所以我們要求的是 x - (sum - x) = S

x = (S + sum) / 2

此時問題就轉化為，裝滿容量為x揹包，有幾種方法。

大家看到(S + sum) / 2 應該擔心計算的過程中向下取整有沒有影響。

這麼擔心就對了，例如sum 是5，S是2的話其實就是無解的，所以：

if ((S + sum) % 2 == 1) return 0; // 此時沒有方案

看到這種表示式，應該本能的反應，兩個int相加數值可能溢位的問題，當然本題並沒有溢位。

再回歸到01揹包問題。

這次和之前遇到的揹包問題不一樣了，之前都是求容量為j的揹包，最多能裝多少。

本題則是裝滿有幾種方法。其實這就是一個組合問題了。

確定dp陣列以及下標的含義

dp[j] 表示：填滿j（包括j）這麼大容積的包，有dp[i]種方法

其實也可以使用二維dp陣列來求解本題，dp[i][j]：使用 下標為[0, i]的nums[i]能夠湊滿j（包括j）這麼大容量的包，有dp[i][j]種方法。

下面我都是統一使用一維陣列進行講解， 二維降為一維（滾動陣列），其實就是上一層複製下來，這個我在動態規劃：關於01揹包問題，你該瞭解這些！（滾動陣列）也有介紹。

不考慮nums[i]的情況下，填滿容量為j - nums[i]的揹包，有dp[j - nums[i]]中方法。

那麼只要搞到nums[i]的話，湊成dp[j]就有dp[j - nums[i]] 種方法。

舉一個例子,nums[i] = 2：dp[3]，填滿揹包容量為3的話，有dp[3]種方法。

那麼只需要搞到一個2（nums[i]），有dp[3]方法可以湊齊容量為3的揹包，相應的就有多少種方法可以湊齊容量為5的揹包。

那麼需要把 這些方法累加起來就可以了，dp[i] += dp[j - nums[j]]

所以求組合類問題的公式，都是類似這種：

dp[j] += dp[j - nums[i]]

這個公式在後面在講解揹包解決排列組合問題的時候還會用到！

dp陣列如何初始化

從遞迴公式可以看出，在初始化的時候dp[0] 一定要初始化為1，因為dp[0]是在公式中一切遞推結果的起源，如果dp[0]是0的話，遞迴結果將都是0。

dp[0] = 1，理論上也很好解釋，裝滿容量為0的揹包，有1種方法，就是裝0件物品。

dp[j]其他下標對應的數值應該初始化為0，從遞迴公式也可以看出，dp[j]要保證是0的初始值，才能正確的由dp[j - nums[i]]推匯出來。

確定遍歷順序

在動態規劃：關於01揹包問題，你該瞭解這些！（滾動陣列）中，我們講過對於01揹包問題一維dp的遍歷，nums放在外迴圈，target在內迴圈，且內迴圈倒序。

舉例推導dp陣列

輸入：nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

dp陣列狀態變化如下：

494.目標和

C++程式碼如下：

本地還是有點難度，大家也可以記住，在求裝滿揹包有幾種方法的情況下，遞推公式一般為：

dp[j] += dp[j - nums[i]];

後面我們在講解完全揹包的時候，還會用到這個遞推公式！

我是程式設計師Carl，個人主頁：https://github.com/youngyangyang04

這裡每天8:35準時推送一道經典演算法題目，我選擇的每道題目都不是孤立的，而是由淺入深，環環相扣，幫你梳理演算法知識脈絡，輕鬆學演算法！