⚡Flashcard Drill➔
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

  1. The target is sum(nums) / k, which must be an integer.
  2. 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).
  3. Prune with: overflow of the target, duplicate values at the same level, and the symmetry break when a bucket is empty.
  4. 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 used check: 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 k non-empty subsets, which the bucket-filling formulation guarantees.
  • Forgetting the total % k check: 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems