Leetcode 698. Partition to K Equal Sum Subsets

Problem

You are given an array of positive integers and an integer k. Your task is to determine whether it's possible to divide the array into exactly k non-empty groups where each group has the same sum.

Each element must belong to exactly one group, and all elements must be used.

Requirements

1. Return true if the array can be partitioned into k equal-sum subsets
2. Return false otherwise
3. Each element must be used exactly once
4. All k subsets must be non-empty

Constraints

• 1 ≤ k ≤ nums.length ≤ 16
• 1 ≤ nums[i] ≤ 10,000
• The frequency of each element is in the range [1, 4]

Examples

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 Output: true Explanation: It's possible to divide into 4 subsets with equal sum 5: [5], [1, 4], [2, 3], [2, 3]

Example 2:

Input: nums = [1, 2, 3, 4], k = 3 Output: false Explanation: The total sum is 10, which cannot be evenly divided by 3.

Example 3:

Input: nums = [2, 2, 2, 2, 3, 4, 5], k = 4 Output: true Explanation: One valid partition is [5], [4], [2, 2], [2, 3], each with sum 5.

Hint 1: Initial Checks Before attempting to partition, verify two necessary conditions:

1. Is the total sum divisible by k?
2. Is any single element larger than the target sum per subset?

If either check fails, return false immediately.

Hint 2: Search Strategy Think about this as filling k buckets to a target capacity. You can use backtracking to try placing each number into different buckets. Consider sorting the array in descending order first - this helps fail faster when a configuration is impossible.

Hint 3: State Tracking Use a visited array or bitmask to track which elements have been assigned to subsets. When building subsets, once a subset reaches the target sum, start building the next one from scratch with the remaining elements.

Full Solution `` Approach:

This solution uses backtracking with aggressive pruning to explore the search space efficiently:

1. Initial validation: Check if the total sum is divisible by k and no element exceeds the target sum per subset.

2. Sorting optimization: Sort the array in descending order. This allows us to fail faster when a configuration is impossible, as larger numbers are more constraining.

3. Backtracking strategy: We fill k buckets sequentially. For each bucket, we try adding unused elements until we reach the target sum, then move to the next bucket.

4. Key pruning techniques:

   • Skip elements that would exceed the target sum
   • When starting a new bucket, if the first element we try doesn't lead to a solution, no other element will either (due to sorting)
   • Skip duplicate values to avoid redundant exploration

5. State tracking: Use a boolean array to mark which elements have been assigned to subsets.

Time Complexity: O(k · 2^n) in the worst case, where n is the array length. Each element can be in or out of the current subset, and we explore k subsets.

Space Complexity: O(n) for the recursion stack and the used array.