[LeetCode] #698. Partition to K Equal Sum Subsets

-

題目

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

直覺解

構想：

把 nums 加總後除以 k，算出每個 subsets 要達到的總和是多少。

要分成 k 個 subset，那就迭代 nums 四次。每次都從 nums[0] 開始迭代，迭代到的每個數，如果加進來不會超過 target，就把該數加進來，然後從 nums 裡把用過的數刪掉（用 for 迭代，一邊迭代一邊刪東西，會有元素在迭代過程中被跳過去，所以採用的方式是，沒被用到的數就加進去新陣列裡面，下次就迭代新陣列）。如果加到剛好等於 target，那就找到一個符合題目要求的 subset。

若符合題目要求的 subset 不足 k 個，就回傳 False。

python 3 實作（失敗）：

class Solution: 

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: 

        target, remainder = divmod(sum(nums), k) 

        if remainder != 0: 

            return False 

         

        subset_count = 0 

        for i in range(k): 

            total = 0 

            new_nums = [] 

            for index, num in enumerate(nums): 

                if total + num <= target: 

                    total += num 

                    if total == target: 

                        subset_count += 1 

                        new_nums.extend(nums[index+1:]) 

                        break 

                else: 

                    new_nums.append(num) 

            nums = new_nums 

             

        if subset_count == k: 

            return True 

        else: 

            return False

Submission Detail

Input:
[1,1,1,1,2,2,2,2]
4

Output: false

Expected: true

失敗原因

適當的 subset 組合是 (1, 2), (1, 2), (1, 2), (1, 2)，但我一開始找到的是組合是 (1, 1, 1), (1, 2)，所以就湊不齊 4 個 subset 了。

構想：

把 nums sort，每次加總的時候從最大的開始加。把迴圈從 for 改成 while，並且從 nums[-1] 往前迭代，這樣邊刪東西邊迭代的的時候，就不會有元素被跳過去了。

python 3 實作（失敗）：

class Solution: 

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: 

        target, remainder = divmod(sum(nums), k) 

        if remainder != 0: 

            return False 

         

        subset_count = 0 

        nums.sort() 

        for i in range(k): 

            total = 0 

            new_nums = [] 

            i = len(nums) - 1 

            while i >= 0: 

                if total + nums[i] <= target: 

                    total += nums[i] 

                    del nums[i] 

                    if total == target: 

                        subset_count += 1 

                i -= 1 

             

        if subset_count == k: 

            return True 

        else: 

            return False

Submission Detail

Input:
[3522,181,521,515,304,123,2512,312,922,407,146,1932,4037,2646,3871,269]
5

Output: false

Expected: true

失敗原因

適當的 subset 組合是 (4037, 407),(3871, 304, 269), (3522, 922), (2646, 521, 515, 312, 181, 146, 123), (2512, 1932)

但我找到的是 (4037, 407), (3522, 922), (2512, 1932)。在找的過程中總和不是 target 卻依然被刪掉的 subset 是 (3871, 521), (2646, 515, 312, 304, 269, 181, 146)，nums 剩下 [123]，所以就湊不齊 5 個 subset 了。

⋯⋯好吧我終於明白這一題難在哪裡了，我之前真是太天真了。不能因為加起來不會超過 target 就粗暴地直接把該數字加進去然後刪掉。

研究別人的解

來源：Python DFS

研究重點：我想到的「不要重複使用同一個 nums[i]」 的方式，是用完後就把他從 nums 裡刪掉。他沒有刪東西，那他是怎麼避免重複使用同一個 nums[i]？他怎麼確保 nums[i] 有放在合適的 subset 裡？

別人的 python 3 實作（已加上研究用的 print）：

class Solution: 

    @staticmethod 

    def canPartitionKSubsets(nums, k): 

        target, m = divmod(sum(nums), k) 

        if m: 

            return False 

        dp, n = [0]*k, len(nums) 

        nums.sort(reverse=True) 

 

        def dfs(i): 

            print('<--') 

            if i == n: 

                print('i == n', 'set(dp):', set(dp)) 

                print('-->') 

                return len(set(dp)) == 1 

            print('i:', i, 'nums[i]:', nums[i]) 

            for j in range(k): 

                dp[j] += nums[i] 

                print('j:', j, 'dp:', dp) 

                if dp[j] <= target and dfs(i+1): 

                    print('-->') 

                    return True 

                dp[j] -= nums[i] 

                if not dp[j]: 

                    print('not dp[j].', 'dp[j]:', dp[j]) 

                    print('-->') 

                    break 

            print('-->') 

            return False 

        return nums[0] <= target and dfs(0)

效能（沒有加 print 的版本）：

Runtime: 44 ms, faster than 84.28% of Python3 online submissions for Partition to K Equal Sum Subsets.
Memory Usage: 14.3 MB, less than 51.31% of Python3 online submissions for Partition to K Equal Sum Subsets.

研究感想

我的寫法是，蒐集完一個 subset 裡要放哪些 nums[i] 之後，再蒐集下一個 subset 裡要放哪些 nums[i]，所以我的 for 迴圈順序是，外圈迭代 range(k)，內圈迭代 range(len(nums))。他則是把一個 nums[i] 放進合適的 subset 後，再把下一個 nums[i] 放進合適的 subset，所以他的做法是，最外層用遞迴函式遍歷 nums，遞迴函式裡面的 for 迴圈則迭代 range(k)>。因為他最外層是迭代 nums，所以他要從 sum 裡面把 nums[i] 減掉就不會重複使用 nums[i] 了，不需要做到「把 nums[i] 從 nums 裡刪掉」的地步。

先把 nums[i] 暫時先放在第一個「加進去後總和不會超過 target」的 subset 裡，然後確定 nums[i+1] 也有合適的 subset 可以安置以後，才真正確定下來 nums[i] 的確要放在這個 subset 裡。如果發現 nums[i+1] 沒有合適的 subset 可以安置，那 nums[i] 就要放到別的 subset 裡。

如果 i == n，代表 nums 裡的所有數字都被放在某個 subset 裡了，此時就檢查是否每個 subset 的總和都相等。若相等的話，len(set(dp)) 會是 1。

關於 if not dp[j]: break

試著把此行程式碼刪掉，結果效能變成了 Runtime: 2448 ms, faster than 9.12% of Python3 online submissions。看來這一行應該是為效能而增加的，例如盡快脫離不可能的 subset 組合。

試著用 nums = [2, 2, 2, 2, 2, 2], k = 4 這組 input，觀察這行程式碼如何增進效能。

subset 裡面連第一個數字都放不進去的時候，會用到這行程式碼。主要是因為 dfs(i+1) 是 false 而放不進去。不可能是因為總和大於 target 而放不進去，因為如果 nums[i] 本身就大於 target 的話，這個函式早在 return nums[0] <= target and dfs(0) 時就 return False 了，根本沒辦法執行到 if not dp[j]: break 這一行。過程如下列程式碼註釋處：

def dfs(i): 

      if i == n: 

          return len(set(dp)) == 1 

      for j in range(k): 
 
          dp[j] += nums[i] # dp[j] 原本是 0，現在加上了 nums[i] 

          if dp[j] <= target and dfs(i+1): 

              return True 

          dp[j] -= nums[i] # nums[i] 不適合放在 j 這個 subset，所以把 nums[i] 減掉，變回 0 

          if not dp[j]: break # 0 是 falsy，所以符合 if 設定的條件 

      return False

放數字到 subset 時，是前面的 subset 都放不進去，才輪得到放在後面的 subset。前面的 subset 都放不進去 nums[i] 了，後面的 subset 在 sum 明明是 0 （代表還沒有放任何數字）的情況下卻也放不進去的話，代表 nums[i] 是真的放不進任何一個 subset，所以 return False。

研究別人的解

來源：Python Solution

別人的 python 3 實作：

class Solution: 

    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: 

         

        target, remainder = divmod(sum(nums), k) 

         

        if remainder: return False  

         

        def searchSubsets(subsets): 

            if not nums: return True  

             

            v = nums.pop() 

             

            for i, val in enumerate(subsets): 

                if val + v <= target: 

                    subsets[i] += v 

                    if searchSubsets(subsets): 

                        return True 

                    # backtrack 

                    subsets[i] -= v 

                if not subsets: 

                    break 

             

            # backtrack 

            nums.append(v) 

            # This combination did not work return False and backtrack or go back to calling function 

            return False  

         

        nums.sort() 

         

        if nums and nums[-1] > target: 

            return False 

        if nums and nums[-1] == target: 

            nums.pop() 

            k -= 1 

         

        return searchSubsets([0] * k)

效能：

Runtime: 1696 ms, faster than 15.16% of Python3 online submissions for Partition to K Equal Sum Subsets.
Memory Usage: 14.5 MB, less than 15.44% of Python3 online submissions for Partition to K Equal Sum Subsets.

研究感想

解題構想跟上一個解差不多。在實作上不太一樣的地方：

  • 上一個解：if i == n: return len(set(dp)) == 1
    這一個解：if not nums: return True

    把上一個解改成 if i == n: return True 的話也能 submit 成功

  • 上一個解：if not dp[j]: break
    這一個解：if not subsets: break

    把這一個解改成 if not subsets[i]: break 的話效能改善很多：
    Runtime: 36 ms, faster than 96.35% of Python3 online submissions for Partition to K Equal Sum Subsets.
    Memory Usage: 14.2 MB, less than 75.37% of Python3 online submissions for Partition to K Equal Sum Subsets.

Comments

Post a Comment

Popular posts from this blog

資料關聯

-
以飲料店的商品種類為例，假設我們現在有飲料和杯子兩種資料。 飲料： id name 1 綠茶 2 紅茶 3 青草茶 杯子： id size 1 500 2 600 3 700 一對一（One to One） 若飲料和杯子是一對一的關係，那麼情況就類似這樣： 綠茶只用 500 cc 的杯子裝 紅茶只用 600 cc 的杯子裝 青草茶只用 700 cc 的杯子裝 一種飲料只有一個尺寸的杯子，而且一個尺寸的杯子也只對應到一種飲料。在這種情況下要建立關聯，有下列兩種方式，擇一即可。這兩種做法在技術上效果是一樣的，不過語意解讀上可能不太一樣。 把關聯欄位加在飲料（語意上，是飲料有杯子這個屬性） 把關聯欄位加在杯子（語意上，是杯子有飲料這個屬性） 把關聯欄位加在飲料的資料表： id name cup_id 1 綠茶 1 2 紅茶 2 3 青草茶 3 把關聯欄位加在杯子的資料表： id size drink_id 1 500 1 2 600 2 3 700 3 一對多（One to Many） 若飲料和杯子是一對多的關係，那麼情況就類似這樣： 綠茶用 500 cc、700 cc 的杯子裝 紅茶只用 600 cc 的杯子裝 一種飲料有許多尺寸的杯子，而且一個尺寸的杯子只對應到一種飲料。 或者是這樣： 綠茶、紅茶、青草茶都只用 500 cc 的杯子裝 一個尺寸的杯子對應到許多種飲料，而且一種飲料只有一個尺寸的杯子。 在這種情況下要建立關聯，一般會選擇加在多的那一邊。如果加在少的那一...
Read more

程式設計相關社群、活動

-
網頁開發 網頁開發雜記 PJCHENder網頁開發咩腳 Backend 台灣 (Backend Tw) Taiwan Backend Group Backend.tw (友善版) Google Chrome Developers 語言 Python Taiwan JavaScript.tw Kotlin： Kraftsman：Coding 職人塾 資安 網路攻防戰 資安解壓縮 Infosec Decompress DEVCORE 如何成為駭客 (資安研討會、社群與網路資源篇) Cymetrics Tech Blog （有胡立大大） 台灣電腦網路危機處理暨協調中心 UCCU Hacker HITCON GIRLS 資安人科技網 個人或公司 資料科學家的工作日常 Ant Yi-Feng Tzeng 偷米騎巴哥 John Liu 的軟體工程思維 Will 保哥的技術交流中心 新加坡商鈦坦科技 Line 的技術部落格 區塊鏈李婷婷 、 FB 、 line 群 管理 TGONetworks 91 敏捷開發之路 技術管理者交流社團 課程 軟體開發學習資訊分享 Udemy 限時免費課程 cs50 中文討論區 Lidemy 鋰學院 商業思維學院 未分類 NEX Foundation 台灣未來基金會 iThome FB Daodu Tech 科技島讀 ∞ Lab 無限大實驗室．金融科技第一站 DevOps Taiwan Chatbot Developers Taiwan 軟體開發的疑難雜症交流區 年會 Hacks In Taiwan 台灣駭客年會 FB 台灣資安大會 cybersec 2021 開源人年會 COSCUP 2021 Python 年會 PyCon 2021 ModernWeb 開發者年會 2021 Javascript 開發者年會 FB: JSDC Taiwan 敏捷年會 Agile Summit 20...
Read more

TCP/ IP 通訊協定

-
為什麼要有通訊協定 不同機器之間，若要能夠溝通的話，需要大家都使用相同的語言。所有人都遵守通訊協定，就不會出現語言隔閡。 什麼是 TCP/ IP 通訊協定 要實現「不同機器之間能夠溝通」，從硬體到軟體，有許多工作要完成。為了讓這份工作比較容易進行，所以將工作拆分成好幾個部分，各自獨立完成；以後若要維護的話，哪個部分有問題，只要維修那個部分就好，不必把所有部分都拿出來檢查，降低維修難度。 至於工作到底要怎麼拆分，不同的模型有不同的建議。OSI（Open System Interconnection）模型切成七層工作，DoD（Department of Defense Model）模型則是切成四層，每一層都有不同的通訊協定。雖然目前實作上通常不是採用 OSI 模型，但為了方便理解「不同機器之間能夠溝通」的機制，通常會用 OSI 模型講解，也會試著將 DoD 模型對應到 OSI 模型。 DoD 模型中有許多通訊協定，不過以 TCP、IP 這兩個通訊協定最具有代表性，所以 DoD 模型又稱為 TCP/ IP 模型。TCP 協定對應到 OSI 模型中的傳送層，IP 協定則是對應到網路層。 TCP、IP 通訊協定負責什麼工作 TCP 協定 發送端的 TCP，和接收端的 TCP，會先進行三向交握，確認彼此能夠順利傳輸資料，才正式開始傳輸資料。 我們可以把要傳輸的資料想像成要郵寄的包裹，郵寄時，包裹會有尺寸或重量的限制，同樣地，傳輸的資料也會有大小的限制。如果資料太大了，TCP 會拆分成小包裹，並且幫每個小包裹編號（以便接收端最後能把小包裹還原成大包裹），並注意是否每一個小包裹都成功送達，若沒有成功送達，TCP 會再補上缺少的小包裹。如果資料太小了，TCP 會幫包裹灌水，以符合大小的下限。 IP 協定 IP 位址就像收件地址，以便確認要將包裹送去哪個主機。IP 位址目前有兩種版本，IPv4 用 32 位元儲存地址，IPv6 用 128 位元儲存地址。所以 IPv6 有比較多的地址可以分配給不同的主機。 IPv4 以 IPv4 而言，位址可以切成兩個部分，第一部分代表 Net ID，第二部分代表 Host ID。相同的 Net ID，代表主機位在相同的 IP 網段，相同 IP 網段的主機之間可以用廣播的方式傳遞資料，而不必透過路由。可以從 N...
Read more