# 0494. 目標和 ## 題目地址(494. 目標和) <https://leetcode-cn.com/problems/target-sum/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個非負整數數組，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。 提示： 數組非空，且長度不會超過 20 。 初始的數組的和不會超過 1000 。 保證返回的最終結果能被 32 位整數存下。 ``` ``` ## 前置知識 - 動態規劃 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 題目是給定一個數組，讓你在數字前面添加 `+`或者`-`，使其和等于 target.  暴力法的時間復雜度是指數級別的，因此我們不予考慮。我們需要換種思路. 我們將最終的結果分成兩組，一組是我們添加了`+`的，一組是我們添加了`-`的。  如上圖，問題轉化為如何求其中一組，我們不妨求前面標`+`的一組 > 如果求出一組，另一組實際就已知了，即總集和這一組的差集。 通過進一步分析，我們得到了這樣的關系：  因此問題轉化為，求解`sumCount(nums, target)`,即 nums 數組中能夠組成 target 的總數一共有多少種，這是一道我們之前做過的題目，使用動態規劃可以解決。 ## 關鍵點解析 - 對元素進行分組，分組的依據是符號， 是`+` 或者 `-` - 通過數學公式推導可以簡化我們的求解過程，這需要一點`數學知識和數學意識` ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=494 lang=javascript * * [494] Target Sum * */</span> <span class="hljs-title">// 這個是我們熟悉的問題了</span> <span class="hljs-title">// 我們這里需要求解的是nums里面有多少種可以組成target的方式</span> <span class="hljs-keyword">var</span> sumCount = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums, target</span>) </span>{ <span class="hljs-title">// 這里通過觀察，我們沒必要使用二維數組去存儲這些計算結果</span> <span class="hljs-title">// 使用一維數組可以有效節省空間</span> <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>(target + <span class="hljs-params">1</span>).fill(<span class="hljs-params">0</span>); dp[<span class="hljs-params">0</span>] = <span class="hljs-params">1</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = target; j >= nums[i]; j--) { dp[j] += dp[j - nums[i]]; } } <span class="hljs-keyword">return</span> dp[target]; }; <span class="hljs-keyword">const</span> add = nums => nums.reduce((a, b) => (a += b), <span class="hljs-params">0</span>); <span class="hljs-title">/** * @param {number[]} nums * @param {number} S * @return {number} */</span> <span class="hljs-keyword">var</span> findTargetSumWays = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums, S</span>) </span>{ <span class="hljs-keyword">const</span> sum = add(nums); <span class="hljs-keyword">if</span> (sum < S) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">if</span> ((S + sum) % <span class="hljs-params">2</span> === <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">0</span>; <span class="hljs-keyword">return</span> sumCount(nums, (S + sum) >> <span class="hljs-params">1</span>); }; ``` ``` **復雜度分析** - 時間復雜度：O(N?target)O(N \* target)O(N?target) - 空間復雜度：O(target)O(target)O(target) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。  ## 擴展 如果這道題目并沒有限定所有的元素以及 target 都是正數怎么辦？