NeetCode #508LC-698MediumBacktrackingNC 250
← Back to All Problems#508 · #698 · Partition to K Equal Sum Subsets(划分为 k 个相等的子集)
📌 Problem Statement & Constraints
Given an integer array
nums and an integer k, return whether it is possible to divide the array into k non-empty subsets with equal sums. Constraints: 1 <= k <= nums.length <= 16, 1 <= nums[i] <= 10^4.💡 Core Algorithmic Approaches
- The target is
sum(nums) / k, which must be an integer. - Sort descending, then fill the buckets one at a time: when a bucket reaches the target, start the next one from index 0 (skipping used elements).
- Prune with: overflow of the target, duplicate values at the same level, and the symmetry break when a bucket is empty.
- The element-index approach (rather than a bitmask over subsets) is the standard accepted solution.
💻 Benchmark Python3 Implementation
class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
total = sum(nums)
if total % k:
return False
target = total // k
nums.sort(reverse=True)
if nums[0] > target:
return False
used = [False] * len(nums)
def dfs(start: int, cur: int, groups: int) -> bool:
if groups == k:
return True # all k buckets filled
if cur == target:
return dfs(0, 0, groups + 1) # start the next bucket
for i in range(start, len(nums)):
if used[i] or cur + nums[i] > target:
continue
# skip duplicates already considered at this level
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True
if dfs(i + 1, cur + nums[i], groups):
return True
used[i] = False
return False
return dfs(0, 0, 0)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(k * 2^n) worst case, with heavy pruning from the sorting and duplicate skipping.
💾 Space Complexity
O(n) for the used array and the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Restarting from index 0 without the
usedcheck: elements would be reused. - Omitting the duplicate skip: many equivalent branches would be explored.
- Not sorting descending: the large elements are the most constrained, so placing them first prunes fastest.
- Allowing an empty subset: the problem requires
knon-empty subsets, which the bucket-filling formulation guarantees. - Forgetting the
total % kcheck: the target must be an integer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.