MediumRating 1677

698. Partition to K Equal Sum Subsets

backtrackingbit-manipulationdynamic-programming

解題說明

Partition to K Equal Sum Subsets

題目描述：給定整數陣列 nums 和整數 k，判斷是否能將陣列分成 k 個非空子集，使得每個子集的元素和相等。

解題思路：先計算目標子集和 target = sum(nums) / k；若不能整除，直接回傳 false。接著用回溯法 + 位元遮罩追蹤哪些元素已被使用。

核心想法：將 nums 降序排列（優先嘗試較大的數，更快遇到剪枝），用 used 位元遮罩標記已放入子集的元素，cur_sum 記錄當前子集的累計和。若 cur_sum == target，當前子集完成，開始填充下一個子集（k 減一）；若 k == 1，代表所有子集均已完成，回傳 true。

關鍵剪枝：

若加入某個元素後 cur_sum > target，跳過。
若當前元素與前一個被跳過的元素值相同，跳過（避免等值元素的重複搜尋）。
搭配記憶化：用 memo[used] 儲存當 used 狀態時是否可行，避免重複計算。

C++ 解法

複雜度分析

時間複雜度：O(k × 2^n)——位元遮罩共有 2^n 個狀態，記憶化確保每個狀態只計算一次；每個狀態需 O(n) 時間嘗試所有元素，但 k 的層數由記憶化合併，整體約 O(n × 2^n)。

空間複雜度：O(2^n)——記憶化 HashMap 最多儲存 2^n 個狀態；遞迴深度最多 O(n)（每個元素被放入一次），call stack 為 O(n)。

虛擬碼

1. Compute total = sum(nums). If total % k != 0, return false.
2. target = total / k. Sort nums descending.
3. If nums[0] > target, return false.
4. Initialize memo = {}, used = 0.
5. backtrack(used, k_remaining=k, cur_sum=0):
   a. If k_remaining == 1: return true.
   b. If cur_sum == target: return backtrack(used, k_remaining-1, 0).
   c. If used in memo: return memo[used].
   d. prev = -1. For each i not in used:
      - If nums[i] == prev: skip (duplicate at this level).
      - If cur_sum + nums[i] > target: skip.
      - Set prev = nums[i].
      - Recurse with used | (1<<i), k_remaining, cur_sum + nums[i].
      - If recurse returns true: memo[used] = true, return true.
   e. memo[used] = false. Return false.
6. Return backtrack(0, k, 0).

其他解法

方法一：純回溯（無記憶化） 不使用 memo，僅靠排序和剪枝。最壞情況 O(k × n!)，但在大多數測試案例中配合降序排列 + 剪枝仍能通過。程式碼更簡潔，適合理解基本回溯框架。

方法二：Bitmask DP（Bottom-up） dp[mask] 表示「放入 mask 中元素後，各子集是否都未超過 target 且當前填充子集的累計和為 dp[mask] % target」。從 mask=0 開始，逐一嘗試加入元素轉移狀態。時間 O(n × 2^n)，空間 O(2^n)，無遞迴開銷，適合迭代式實作。

方法三：從「桶」的角度回溯 維護 k 個桶（bucket），逐一將 nums 中的元素分配到某個桶中，確保每個桶最終恰好為 target。等效元素的桶用剪枝避免重複（若兩個桶目前和相同，只嘗試其中一個）。時間同為指數級，但在某些分布下比「以元素為主」的方法更快。

延伸思考

若 k = 2，問題退化為「判斷是否能將陣列分成兩個和相等的子集」（LC 416），此時動態規劃的 O(n × sum) 解法比回溯快多少？
記憶化的 used 位元遮罩在此題中代表「哪些元素已被分配」而非「當前子集狀態」——為什麼即便 k_remaining 不同，相同 used 的結果仍然一致？（提示：想想 target 的意義）
如果陣列中存在重複元素，現有的「跳過相同值」剪枝是否足夠？還是需要像全排列去重一樣先排序後才能正確剪枝？

解題說明

Partition to K Equal Sum Subsets

題目描述：給定整數陣列 nums 和整數 k，判斷是否能將陣列分成 k 個非空子集，使得每個子集的元素和相等。

解題思路：先計算目標子集和 target = sum(nums) / k；若不能整除，直接回傳 false。接著用回溯法 + 位元遮罩追蹤哪些元素已被使用。

關鍵剪枝：

若加入某個元素後 cur_sum > target，跳過。
若當前元素與前一個被跳過的元素值相同，跳過（避免等值元素的重複搜尋）。
搭配記憶化：用 memo[used] 儲存當 used 狀態時是否可行，避免重複計算。

複雜度分析

空間複雜度：O(2^n)——記憶化 HashMap 最多儲存 2^n 個狀態；遞迴深度最多 O(n)（每個元素被放入一次），call stack 為 O(n)。

虛擬碼

1. Compute total = sum(nums). If total % k != 0, return false. 2. target = total / k. Sort nums descending. 3. If nums[0] > target, return false. 4. Initialize memo = {}, used = 0. 5. backtrack(used, k_remaining=k, cur_sum=0): a. If k_remaining == 1: return true. b. If cur_sum == target: return backtrack(used, k_remaining-1, 0). c. If used in memo: return memo[used]. d. prev = -1. For each i not in used: - If nums[i] == prev: skip (duplicate at this level). - If cur_sum + nums[i] > target: skip. - Set prev = nums[i]. - Recurse with used | (1<<i), k_remaining, cur_sum + nums[i]. - If recurse returns true: memo[used] = true, return true. e. memo[used] = false. Return false. 6. Return backtrack(0, k, 0).

其他解法

延伸思考

若 k = 2，問題退化為「判斷是否能將陣列分成兩個和相等的子集」（LC 416），此時動態規劃的 O(n × sum) 解法比回溯快多少？
記憶化的 used 位元遮罩在此題中代表「哪些元素已被分配」而非「當前子集狀態」——為什麼即便 k_remaining 不同，相同 used 的結果仍然一致？（提示：想想 target 的意義）
如果陣列中存在重複元素，現有的「跳過相同值」剪枝是否足夠？還是需要像全排列去重一樣先排序後才能正確剪枝？