<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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">``` <span class="hljs-keyword">var</span> canPartition = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">let</span> sum = nums.reduce((acc, num) => acc + num, <span class="hljs-params">0</span>); <span class="hljs-keyword">if</span> (sum % <span class="hljs-params">2</span>) { <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } sum = sum / <span class="hljs-params">2</span>; <span class="hljs-keyword">return</span> dfs(nums, sum, <span class="hljs-params">0</span>); }; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">dfs</span>(<span class="hljs-params">nums, target, cur</span>) </span>{ <span class="hljs-keyword">if</span> (target < <span class="hljs-params">0</span> || cur > nums.length) { <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } <span class="hljs-keyword">return</span> ( target === <span class="hljs-params">0</span> || dfs(nums, target - nums[cur], cur + <span class="hljs-params">1</span>) || dfs(nums, target, cur + <span class="hljs-params">1</span>) ); } ``` ``` 不出所料,這里是超時了,我們看看有沒優化空間 1. 如果 nums 中最大值 > 2/sum, 那么肯定無解 2. 在搜索過程中,我們對每個數都是取或者不取,并且數組中所有項都為正數。我們設取的數和為 `pickedSum`,不難得 pickedSum <= 2/sum, 同時要求丟棄的數為 `discardSum`,不難得 pickedSum <= 2 / sum。 我們同時引入這兩個約束條件加強剪枝: 優化后的代碼如下 ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> canPartition = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">let</span> sum = nums.reduce((acc, num) => acc + num, <span class="hljs-params">0</span>); <span class="hljs-keyword">if</span> (sum % <span class="hljs-params">2</span>) { <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } sum = sum / <span class="hljs-params">2</span>; nums = nums.sort((a, b) => b - a); <span class="hljs-keyword">if</span> (sum < nums[<span class="hljs-params">0</span>]) { <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } <span class="hljs-keyword">return</span> dfs(nums, sum, sum, <span class="hljs-params">0</span>); }; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">dfs</span>(<span class="hljs-params">nums, pickRemain, discardRemain, cur</span>) </span>{ <span class="hljs-keyword">if</span> (pickRemain === <span class="hljs-params">0</span> || discardRemain === <span class="hljs-params">0</span>) { <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; } <span class="hljs-keyword">if</span> (pickRemain < <span class="hljs-params">0</span> || discardRemain < <span class="hljs-params">0</span> || cur > nums.length) { <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } <span class="hljs-keyword">return</span> ( dfs(nums, pickRemain - nums[cur], discardRemain, cur + <span class="hljs-params">1</span>) || dfs(nums, pickRemain, discardRemain - nums[cur], cur + <span class="hljs-params">1</span>) ); } ``` ``` 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">``` <span class="hljs-keyword">var</span> canPartition = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">let</span> sum = nums.reduce((acc, num) => acc + num, <span class="hljs-params">0</span>); <span class="hljs-keyword">if</span> (sum % <span class="hljs-params">2</span>) { <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } <span class="hljs-keyword">else</span> { sum = sum / <span class="hljs-params">2</span>; } <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>.from(nums).map(() => <span class="hljs-params">Array</span>.from({ length: sum + <span class="hljs-params">1</span> }).fill(<span class="hljs-params">false</span>) ); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { dp[i][<span class="hljs-params">0</span>] = <span class="hljs-params">true</span>; } <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < dp.length - <span class="hljs-params">1</span>; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">0</span>; j < dp[<span class="hljs-params">0</span>].length; j++) { dp[i + <span class="hljs-params">1</span>][j] = j - nums[i] >= <span class="hljs-params">0</span> ? dp[i][j] || dp[i][j - nums[i]] : dp[i][j]; } } <span class="hljs-keyword">return</span> dp[nums.length - <span class="hljs-params">1</span>][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">``` <span class="hljs-keyword">var</span> canPartition = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">nums</span>) </span>{ <span class="hljs-keyword">let</span> sum = nums.reduce((acc, num) => acc + num, <span class="hljs-params">0</span>); <span class="hljs-keyword">if</span> (sum % <span class="hljs-params">2</span>) { <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } sum = sum / <span class="hljs-params">2</span>; <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>.from({ length: sum + <span class="hljs-params">1</span> }).fill(<span class="hljs-params">false</span>); dp[<span class="hljs-params">0</span>] = <span class="hljs-params">true</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 = sum; j > <span class="hljs-params">0</span>; j--) { dp[j] = dp[j] || (j - nums[i] >= <span class="hljs-params">0</span> && dp[j - nums[i]]); } } <span class="hljs-keyword">return</span> 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">``` <span class="hljs-title">/** * @param {number} amount * @param {number[]} coins * @return {number} */</span> <span class="hljs-keyword">var</span> change = <span class="hljs-function"><span class="hljs-keyword">function</span> (<span class="hljs-params">amount, coins</span>) </span>{ <span class="hljs-keyword">const</span> dp = <span class="hljs-params">Array</span>.from({ length: amount + <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 < coins.length; i++) { <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> j = <span class="hljs-params">1</span>; j <= amount; j++) { dp[j] = dp[j] + (j - coins[i] >= <span class="hljs-params">0</span> ? dp[j - coins[i]] : <span class="hljs-params">0</span>); } } <span class="hljs-keyword">return</span> 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)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看