LeetCode 698: Partition to K Equal Sum Subsets Solution in Python – A Step-by-Step Guide

What Is LeetCode 698: Partition to K Equal Sum Subsets?

In LeetCode 698: Partition to K Equal Sum Subsets, you’re given an integer array nums and an integer k, and your task is to determine if it’s possible to partition nums into k non-empty subsets, each with the same sum. Return True if possible, False otherwise. For example, with nums = [4, 3, 2, 3, 5, 2, 1] and k = 4, the total sum is 20, and dividing by 4 gives a target sum of 5 per subset. You can form [5], [4], [3, 2], and [3, 2, 1], all summing to 5, so return True. This problem tests your ability to solve a combinatorial partitioning problem efficiently.

Problem Statement

• Input:
• nums: List of integers.
• k: Integer (number of subsets).
• Output: A boolean—True if partition into k equal-sum subsets is possible, False otherwise.
• Rules:
• Partition nums into k non-empty subsets.
• Each subset must have the same sum.
• Use all elements of nums.

Constraints

• 1 ≤ k ≤ nums.length ≤ 16.
• 1 ≤ nums[i] ≤ 10⁴.

Examples

• Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
• Output: True (Subsets: [5], [4], [3, 2], [3, 2, 1], sum = 5 each)
• Input: nums = [1, 2, 3, 4], k = 3
• Output: False (Sum = 10, not divisible by 3)
• Input: nums = [2, 2, 2, 2], k = 2
• Output: True (Subsets: [2, 2], [2, 2], sum = 4 each)

These examples set the array—let’s solve it!

Understanding the Problem: Partitioning into K Subsets

To solve LeetCode 698: Partition to K Equal Sum Subsets in Python, we need to determine if nums can be split into k non-empty subsets with equal sums. A brute-force approach—trying all possible partitions—would be O(k^n), where n is the array length, impractical for n ≤ 16. Since we’re partitioning with a target sum, backtracking or exhaustive enumeration can optimize this by pruning invalid paths. We’ll use:

• Best Solution (Backtracking with Subset Sums): O(2^n) time, O(n) space—fast and practical.
• Alternative Solution (Brute-Force with All Partitions): O(k^n) time, O(n) space—simple but inefficient.

Let’s start with the backtracking solution, breaking it down for beginners.

Best Solution: Backtracking with Subset Sums

Why This Is the Best Solution

The backtracking with subset sums approach is the top choice for LeetCode 698 because it’s efficient—O(2^n) time with O(n) space—and uses a recursive strategy to assign numbers to k subsets, pruning branches when sums exceed the target or when impossible, leveraging early checks to optimize performance. It fits constraints (n ≤ 16) perfectly and is intuitive once you see the recursion logic. It’s like trying to fit puzzle pieces into k boxes, backtracking when they don’t fit!

How It Works

Think of this as a puzzle fitter:

• Step 1: Validate Input:
• Check if sum(nums) % k == 0, else return False.
• Compute target = sum(nums) / k.
• Step 2: Sort Array:
• Sort nums descending to optimize (place larger numbers first).
• Step 3: Backtracking Function:
• Parameters: index, subsets (list of sums), target.
• Base: If index = len(nums), check if all subsets = target.
• Recurse: Try placing nums[index] in each subset, backtrack if exceeds target.
• Step 4: Early Pruning:
• If num > target or k > n, return False early.
• Step 5: Return Result:
• True if partition found, False otherwise.

It’s like a subset assigner—fit and backtrack!

Step-by-Step Example

Example: nums = [4, 3, 2, 3, 5, 2, 1], k = 4

• Step 1: Validate:
• Sum = 20, 20 % 4 = 0, target = 20 / 4 = 5.
• Step 2: Sort: [5, 4, 3, 3, 2, 2, 1].
• Step 3: Backtrack:
• subsets = [0, 0, 0, 0], index = 0.
• Place 5 in [0]: [5, 0, 0, 0], index = 1.
• Place 4 in [0]: [4, 0, 0, 0], index = 2.
• Place 3 in [0]: [3, 0, 0, 0], index = 3.
• Place 3 in [0]: [3, 0, 0, 0], index = 4.
• Place 2 in [0]: [5, 0, 0, 0], backtrack (exceeds 5).
• Place 2 in [1]: [3, 2, 0, 0], index = 5.
• Place 2 in [1]: [3, 2, 0, 0], index = 6.
• Place 1 in [1]: [3, 3, 0, 0], index = 7, backtrack.
• Place 1 in [2]: [3, 2, 1, 0], backtrack.
• Backtrack to index = 2, try 3 in [1]: [4, 3, 0, 0], index = 3.
• Place 3 in [2]: [4, 3, 3, 0], index = 4.
• Place 2 in [3]: [4, 3, 3, 2], index = 5.
• Place 2 in [1]: [4, 5, 3, 2], index = 6.
• Place 1 in [2]: [4, 5, 4, 2], index = 7.
• Place 2 in [3]: [4, 5, 4, 3], backtrack.
• Continue: Eventually find [5], [4], [3, 2], [3, 2, 1], all sum to 5.
• Step 4: Return True.
• Output: True.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        # Step 1: Validate input
        total = sum(nums)
        if total % k != 0 or k > len(nums):
            return False
        target = total // k
        nums.sort(reverse=True)  # Optimize by starting with larger numbers

        # Step 2: Backtracking function
        def backtrack(index: int, subsets: List[int]) -> bool:
            if index == len(nums):  # All numbers used
                return all(s == target for s in subsets)

            for i in range(k):
                if subsets[i] + nums[index] <= target:
                    subsets[i] += nums[index]
                    if backtrack(index + 1, subsets):
                        return True
                    subsets[i] -= nums[index]  # Backtrack
                    if subsets[i] == 0:  # Prune empty subset branches
                        break
            return False

        # Step 3: Start backtracking
        return backtrack(0, [0] * k)

• Lines 4-8: Validate: Check divisibility and k feasibility, compute target.
• Line 9: Sort: Descending order for optimization.
• Lines 12-24: Backtrack:
• Base: All used, check sums equal target.
• Try each subset, backtrack if exceeds, prune empty subsets.
• Line 27: Start with k zero-sum subsets.
• Time Complexity: O(2^n)—exponential, but pruning helps.
• Space Complexity: O(n)—recursion stack and subsets array.

This is like a puzzle solver—fit and retry!

Alternative Solution: Brute-Force with All Partitions

Why an Alternative Approach?

The brute-force with all partitions approach generates all possible partitions—O(k^n) time, O(n) space. It’s simpler conceptually, trying every way to split the array, but impractical for n ≤ 16 due to exponential growth. It’s like testing every possible group split until one works!

How It Works

Picture this as a partition tester:

• Step 1: Validate sum and k.
• Step 2: Generate partitions:
• Recursively assign each number to one of k subsets.
• Step 3: Check sums:
• If all subsets equal target, return True.
• Step 4: Return result.

It’s like a full enumerator—try and check!

Step-by-Step Example

Example: nums = [4, 3, 2, 3], k = 2

• Step 1: Sum = 12, target = 6.
• Step 2: Try partitions:
• [4, 2] [3, 3]: 6, 6, valid.
• [4, 3] [2, 3]: 7, 5, invalid.
• Step 3: Found valid partition.
• Step 4: Return True.
• Output: True.

Code for Brute-Force Approach

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        # Step 1: Validate input
        total = sum(nums)
        if total % k != 0 or k > len(nums):
            return False
        target = total // k

        # Step 2: Brute-force partition
        def partition(index: int, subsets: List[int]) -> bool:
            if index == len(nums):
                return all(s == target for s in subsets)
            for i in range(k):
                subsets[i] += nums[index]
                if partition(index + 1, subsets):
                    return True
                subsets[i] -= nums[index]
            return False

        # Step 3: Start partition
        return partition(0, [0] * k)

• Lines 4-8: Validate: Check sum and k.
• Lines 11-19: Partition:
• Recursively assign numbers, check sums at end.
• Line 22: Start with k empty subsets.
• Time Complexity: O(k^n)—exponential, tries all assignments.
• Space Complexity: O(n)—recursion stack.

It’s a partition enumerator—try all!

Comparing the Two Solutions

• Backtracking (Best):
• Pros: O(2^n) time, O(n) space, efficient with pruning.
• Cons: Backtracking logic less obvious.
• Brute-Force (Alternative):
• Pros: O(k^n) time, O(n) space, straightforward.
• Cons: Much slower, no pruning.

Backtracking wins for efficiency.

Additional Examples and Edge Cases

• Input: nums = [1], k = 1
• Output: True.
• Input: nums = [1, 2], k = 2
• Output: False.

Backtracking handles these well.

Complexity Breakdown

• Backtracking: Time O(2^n), Space O(n).
• Brute-Force: Time O(k^n), Space O(n).

Backtracking is optimal.

Key Takeaways

• Backtracking: Subset fitting—smart!
• Brute-Force: Full partitioning—clear!
• Puzzles: Solving is fun.
• Python Tip: Recursion rocks—see Python Basics.

Final Thoughts: Solve That Puzzle

LeetCode 698: Partition to K Equal Sum Subsets in Python is a fun partitioning challenge. Backtracking with subset sums offers speed and elegance, while brute-force provides a clear baseline. Want more? Try LeetCode 416: Partition Equal Subset Sum or LeetCode 473: Matchsticks to Square. Ready to partition? Head to Solve LeetCode 698 on LeetCode and split that array today!