416. 分割等和子集

題目鏈接：416. 分割等和子集 - 力扣（LeetCode）

思考：本題要將數組分為兩個子數組，且兩個子數組和相等，因此首先可以想到的條件就是數組可分為兩個，這要求數組元素數量>1，要想兩個子數組和相等，則原始數組和為偶數才行。

處理完上述特殊條件后，需要考慮如何劃分數組。由于要把原始數組劃分為兩個子數組且兩個數組和相等，則每個數組元素和為原始數組總和的一半。令這個總和的一半為target，則需要在原始數組中找到是否存在某個元素等于target，或是存在幾個元素之和為target。

這里要注意的是，本題與在某個數組中尋找是否存在元素target不一樣，因為本題的target不一定是一個元素，可以是多個元素之和，具體是幾個元素之和不確定。因此本題想要直接暴力求解的話，會特別耗時。

因此需要結合01背包思想解決問題，將尋找元素和為target的問題轉化為容量為target的背包，恰好需要裝滿的問題。把所有元素當做可以裝入背包的物品，每個元素占用空間和帶來的價值都是元素數值本身。

初始化dp全0數組，下標表示背包容量，下標對應的數組值表示背包可以裝入物品的最大重量。本題難點在于循環條件和遞推公式，首先要遍歷所有物品，然后依據背包容量，更新背包裝入的物品重量，即：

• 外層循環：遍歷每個數字?num。

• 內層循環：從?target?逆向遍歷到?num（避免重復計算）。

  • 狀態轉移：對于容量?j，選擇是否裝入?num：

    • 不裝：dp[j]?保持不變。

    • 裝：dp[j-num] + num（當前和加上?num?的值）。

  • 取兩者最大值更新?dp[j]。

代碼：

class Solution:def canPartition(self, nums: List[int]) -> bool:n = len(nums)if n <= 1:return Falsetotal = sum(nums)if total % 2 != 0:return Falsetarget = total // 2dp = [0] * 10001for num in nums:for j in range(target, num-1, -1):dp[j] = max(dp[j], dp[j-num]+num)if dp[target] == target:return Truereturn False

698.劃分為k個相等的子集

題目鏈接：698. 劃分為k個相等的子集 - 力扣（LeetCode）

思考：要判斷是否可以將數組分成k個非空子集，且每個子集的和相等，可以按照以下步驟進行：

1. 總和檢查：首先計算數組所有元素的總和。如果總和不能被k整除，直接返回False，因為無法均分。

2. 目標子集和：計算每個子集的目標和，即總和除以k。

3. 排序優化：將數組排序，先處理較大的數，可以更快地剪枝無效路徑。

4. 回溯法：使用回溯法嘗試將數字分配到各個子集中。每次嘗試將當前數字放入一個子集，如果該子集的和不超過目標和，則繼續遞歸處理剩下的數字。如果所有數字都能成功分配，則返回True，否則回溯并嘗試其他可能性。

代碼：

class Solution:def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:n = len(nums)total = sum(nums)if total % k != 0:return Falsenums.sort(reverse=True)  # 排序以便更快剪枝target = total // kif nums[0] > target:return Falseused = [False] * ndef backtrack(start, current_sum, count):if count == k - 1:return Trueif current_sum == target:return backtrack(0, 0, count + 1)for i in range(start, n):if not used[i] and current_sum + nums[i] <= target:used[i] = Trueif backtrack(i + 1, current_sum + nums[i], count):return Trueused[i] = False# 剪枝：跳過相同數字while i + 1 < n and nums[i] == nums[i + 1]:i += 1# 如果當前和為0，說明無法放入任何數，直接失敗if current_sum == 0:breakreturn Falsereturn backtrack(0, 0, 0)

473.火柴拼正方形

題目鏈接：473. 火柴拼正方形 - 力扣（LeetCode）

思考：首先計算所有火柴的總長度 totalLen，如果 totalLen 不是 4 的倍數，那么不可能拼成正方形，返回 false。當 totalLen 是 4 的倍數時，每條邊的邊長為 len=?totalLen/4，用 edges 來記錄 4 條邊已經放入的火柴總長度。對于第 index 火柴，嘗試把它放入其中一條邊內且滿足放入后該邊的火柴總長度不超過 len，然后繼續枚舉第 index+1 根火柴的放置情況，如果所有火柴都已經被放置，那么說明可以拼成正方形。

為了減少搜索量，需要對火柴長度從大到小進行排序。

代碼：

class Solution:def makesquare(self, matchsticks: List[int]) -> bool:totalLen = sum(matchsticks)if totalLen % 4:return Falsematchsticks.sort(reverse=True)edges = [0] * 4def dfs(idx: int) -> bool:if idx == len(matchsticks): # 已經使用了所有火柴return Truefor i in range(4):edges[i] += matchsticks[idx] # 放入火柴if edges[i] <= totalLen // 4 and dfs(idx + 1):return Trueedges[i] -= matchsticks[idx]return Falsereturn dfs(0)