0416. 分割等和子集 · ttttt

# 0416. 分割等和子集 ## 題目地址(416. 分割等和子集) <https://leetcode-cn.com/problems/partition-equal-subset-sum/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個只包含正整數的非空數組。是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。注意: 每個數組中的元素不會超過 100 數組的大小不會超過 200 示例 1: 輸入: [1, 5, 11, 5] 輸出: true 解釋: 數組可以分割成 [1, 5, 5] 和 [11]. 示例 2: 輸入: [1, 2, 3, 5] 輸出: false 解釋: 數組不能分割成兩個元素和相等的子集. ``` ``` ## 前置知識 - DFS - [動態規劃](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ### 思路抽象能力不管是在工程還是算法中都占據著絕對重要的位置。比如上題我們可以抽象為： **給定一個非空數組，和是 sum，能否找到這樣的一個子序列，使其和為 2/sum** 我們做過二數和，三數和，四數和，看到這種類似的題會不會舒適一點，思路更開闊一點。老司機們看到轉化后的題，會立馬想到背包問題，這里會提供**深度優先搜索**和**背包**兩種解法。 ### 深度優先遍歷我們再來看下題目描述，sum 有兩種情況， 1. 如果 sum % 2 === 1, 則肯定無解，因為 sum/2 為小數，而數組全由整數構成，子數組和不可能為小數。 2. 如果 sum % 2 === 0, 需要找到和為 2/sum 的子序列針對 2，我們要在 nums 里找到滿足條件的子序列 subNums。這個過程可以類比為在一個大籃子里面有 N 個球，每個球代表不同的數字，我們用一小籃子去抓取球，使得拿到的球數字和為 2/sum。那么很自然的一個想法就是，對大籃子里面的每一個球，我們考慮取它或者不取它，如果我們足夠耐心，最后肯定能窮舉所有的情況，判斷是否有解。上述思維表述為偽代碼如下： ``` <pre class="calibre18">``` 令 target = sum / 2, nums 為輸入數組, cur 為當前當前要選擇的數字的索引 nums 為輸入數組，target為當前求和目標，cur為當前判斷的數 function dfs(nums, target, cur) 如果target < 0 或者 cur > nums.length return false 否則如果 target = 0, 說明找到答案了，返回true 否則取當前數或者不取，進入遞歸 dfs(nums, target - nums[cur], cur + 1) || dfs(nums, target, cur + 1) ``` ``` 因為對每個數都考慮取不取，所以這里時間復雜度是 O(2 ^ n), 其中 n 是 nums 數組長度， #### javascript 實現 ``` <pre class="calibre18">``` var canPartition = function (nums) { let sum = nums.reduce((acc, num) => acc + num, 0); if (sum % 2) { return false; } sum = sum / 2; return dfs(nums, sum, 0); }; function dfs(nums, target, cur) { if (target < 0 || cur > nums.length) { return false; } return ( target === 0 || dfs(nums, target - nums[cur], cur + 1) || dfs(nums, target, cur + 1) ); } ``` ``` 不出所料，這里是超時了，我們看看有沒優化空間 1. 如果 nums 中最大值 > 2/sum, 那么肯定無解 2. 在搜索過程中，我們對每個數都是取或者不取，并且數組中所有項都為正數。我們設取的數和為 `pickedSum`，不難得 pickedSum <= 2/sum，同時要求丟棄的數為 `discardSum`，不難得 pickedSum <= 2 / sum。我們同時引入這兩個約束條件加強剪枝：優化后的代碼如下 ``` <pre class="calibre18">``` var canPartition = function (nums) { let sum = nums.reduce((acc, num) => acc + num, 0); if (sum % 2) { return false; } sum = sum / 2; nums = nums.sort((a, b) => b - a); if (sum < nums[0]) { return false; } return dfs(nums, sum, sum, 0); }; function dfs(nums, pickRemain, discardRemain, cur) { if (pickRemain === 0 || discardRemain === 0) { return true; } if (pickRemain < 0 || discardRemain < 0 || cur > nums.length) { return false; } return ( dfs(nums, pickRemain - nums[cur], discardRemain, cur + 1) || dfs(nums, pickRemain, discardRemain - nums[cur], cur + 1) ); } ``` ``` leetcode 是 AC 了，但是時間復雜度 O(2 ^ n), 算法時間復雜度很差，我們看看有沒更好的。 ### DP 解法在用 DFS 是時候，我們是不關心取數的規律的，只要保證接下來要取的數在之前沒有被取過即可。那如果我們有規律去安排取數策略的時候會怎么樣呢，比如第一次取數安排在第一位，第二位取數安排在第二位，在判斷第 i 位是取數的時候，我們是已經知道前 i-1 個數每次是否取的所有子序列組合，記集合 S 為這個子序列的和。再看第 i 位取數的情況, 有兩種情況取或者不取 1. 取的情況，如果 target-nums\[i\]在集合 S 內，則返回 true，說明前 i 個數能找到和為 target 的序列 2. 不取的情況，如果 target 在集合 S 內，則返回 true，否則返回 false 也就是說，前 i 個數能否構成和為 target 的子序列取決為前 i-1 數的情況。記 F\[i, target\] 為 nums 數組內前 i 個數能否構成和為 target 的子序列的可能，則狀態轉移方程為 `F[i, target] = F[i - 1, target] || F[i - 1, target - nums[i]]` 狀態轉移方程出來了，代碼就很好寫了，DFS + DP 都可以解，有不清晰的可以參考下 [遞歸和動態規劃](dynamic-programming.html)，這里只提供 DP 解法 #### 偽代碼表示 ``` <pre class="calibre18">``` n = nums.length target 為 nums 各數之和如果target不能被2整除, 返回false 令dp為n * target 的二維矩陣, 并初始為false 遍歷0:n, dp[i][0] = true 表示前i個數組成和為0的可能遍歷 0 到 n 遍歷 0 到 target if 當前值j大于nums[i] dp[i + 1][j] = dp[i][j-nums[i]] || dp[i][j] else dp[i+1][j] = dp[i][j] ``` ``` 算法時間復雜度 O(n\*m), 空間復雜度 O(n\*m), m 為 sum(nums) / 2 #### javascript 實現 ``` <pre class="calibre18">``` var canPartition = function (nums) { let sum = nums.reduce((acc, num) => acc + num, 0); if (sum % 2) { return false; } else { sum = sum / 2; } const dp = Array.from(nums).map(() => Array.from({ length: sum + 1 }).fill(false) ); for (let i = 0; i < nums.length; i++) { dp[i][0] = true; } for (let i = 0; i < dp.length - 1; i++) { for (let j = 0; j < dp[0].length; j++) { dp[i + 1][j] = j - nums[i] >= 0 ? dp[i][j] || dp[i][j - nums[i]] : dp[i][j]; } } return dp[nums.length - 1][sum]; }; ``` ``` 再看看有沒有優化空間，看狀態轉移方程 `F[i, target] = F[i - 1, target] || F[i - 1, target - nums[i]]`第 n 行的狀態只依賴于第 n-1 行的狀態，也就是說我們可以把二維空間壓縮成一維偽代碼 ``` <pre class="calibre18">``` 遍歷 0 到 n 遍歷 j 從 target 到 0 if 當前值j大于nums[i] dp[j] = dp[j-nums[i]] || dp[j] else dp[j] = dp[j] ``` ``` 時間復雜度 O(n\*m), 空間復雜度 O(n) javascript 實現 ``` <pre class="calibre18">``` var canPartition = function (nums) { let sum = nums.reduce((acc, num) => acc + num, 0); if (sum % 2) { return false; } sum = sum / 2; const dp = Array.from({ length: sum + 1 }).fill(false); dp[0] = true; for (let i = 0; i < nums.length; i++) { for (let j = sum; j > 0; j--) { dp[j] = dp[j] || (j - nums[i] >= 0 && dp[j - nums[i]]); } } return dp[sum]; }; ``` ``` 其實這道題和 [leetcode 518](https://leetcode-cn.com/problems/coin-change-2/) 是換皮題，它們都可以歸屬于背包問題 ## 背包問題 ### 背包問題描述有 N 件物品和一個容量為 V 的背包。放入第 i 件物品耗費的費用是 Ci，得到的價值是 Wi。求解將哪些物品裝入背包可使價值總和最大。背包問題的特性是，每種物品，我們都可以選擇放或者不放。令 F\[i, v\]表示前 i 件物品放入到容量為 v 的背包的狀態。針對上述背包，F\[i, v\]表示能得到最大價值，那么狀態轉移方程為 ``` <pre class="calibre18">``` F[i, v] = max{F[i-1, v], F[i-1, v-Ci] + Wi} ``` ``` 針對 416. 分割等和子集這題，F\[i, v\]的狀態含義就表示前 i 個數能組成和為 v 的可能，狀態轉移方程為 ``` <pre class="calibre18">``` F[i, v] = F[i-1, v] || F[i-1, v-Ci] ``` ``` 再回過頭來看下[leetcode 518](https://leetcode-cn.com/problems/coin-change-2/), 原題如下 > 給定不同面額的硬幣和一個總金額。寫出函數來計算可以湊成總金額的硬幣組合數。假設每一種面額的硬幣有無限個。帶入背包思想，F\[i,v\] 表示用前 i 種硬幣能兌換金額數為 v 的組合數，狀態轉移方程為 `F[i, v] = F[i-1, v] + F[i-1, v-Ci]` #### javascript 實現 ``` <pre class="calibre18">``` /** * @param {number} amount * @param {number[]} coins * @return {number} */ var change = function (amount, coins) { const dp = Array.from({ length: amount + 1 }).fill(0); dp[0] = 1; for (let i = 0; i < coins.length; i++) { for (let j = 1; j <= amount; j++) { dp[j] = dp[j] + (j - coins[i] >= 0 ? dp[j - coins[i]] : 0); } } return dp[amount]; }; ``` ``` **復雜度分析** - 時間復雜度：O(amount?len(coins))O(amount \* len(coins))O(amount?len(coins)) - 空間復雜度：O(amount)O(amount)O(amount) ### 參考 [背包九講](https://raw.githubusercontent.com/tianyicui/pack/master/V2.pdf) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)