#698

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Partition to K Equal Sum Subsets

Determine if an integer array can be partitioned into k subsets where each subset sums to the same value using DP and backtracking.

array dynamic programming backtracking bit manipulation memoization

Problem Statement

Given an integer array nums and an integer k, determine whether it is possible to divide the array into k non-empty subsets such that the sum of elements in each subset is equal. Each element must belong to exactly one subset, and subsets can be arranged in any order.

For example, nums = [4,3,2,3,5,2,1] and k = 4 can be partitioned into subsets (5), (1,4), (2,3), (2,3) each summing to 5. If no such division exists, return false. The array length is limited to 16, and elements are positive integers, often repeated.

Examples

Example 1

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

Output: true

It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2

Input: nums = [1,2,3,4], k = 3

Output: false

Example details omitted.

Constraints

1 <= k <= nums.length <= 16
1 <= nums[i] <= 104
The frequency of each element is in the range [1, 4].

Solution Approach

Calculate target subset sum

Sum all elements in nums and divide by k to get the required subset sum. If total sum is not divisible by k, immediately return false as no equal-sum partition is possible.

Backtracking with memoization or bitmask

Use a recursive function to assign elements to subsets, marking used elements. Track current subset sums and backtrack when adding a number exceeds the target. Memoize states using bitmasking to avoid recomputation and reduce exponential complexity.

Prune invalid paths with DP state transitions

Implement state transition dynamic programming to prune search space: skip numbers already used or subsets that exceed the target. This optimization exploits overlapping subproblems and ensures efficient identification of feasible subset assignments.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(k * 2^n) in the worst case using bitmask DP, since each subset assignment can produce 2^n states. Space complexity is O(2^n) for memoization. Backtracking alone may approach O(k^n) without pruning, but DP reduces repeated computation.

What Interviewers Usually Probe

Candidate recognizes need to calculate target sum and checks divisibility early.
Candidate uses bitmask or memoization to avoid recomputation during subset assignments.
Candidate applies pruning to avoid exploring invalid paths exceeding the target sum.

Common Pitfalls or Variants

Common pitfalls

Not checking total sum divisibility by k before recursion, leading to wasted computation.
Failing to track used elements correctly, causing duplicate element usage across subsets.
Skipping memoization or DP optimization, resulting in exponential runtime that times out for n > 12.

Follow-up variants

Partition into 2 equal sum subsets only (simpler case with k=2).
Allow negative numbers, requiring sum balancing and careful DP states.
Count the number of distinct k-partitions with equal sum instead of returning boolean.

FAQ

What is the main pattern used in Partition to K Equal Sum Subsets?

State transition dynamic programming is the main pattern, combined with recursive backtracking to explore subset assignments efficiently.

Can this problem be solved without DP?

Yes, simple backtracking works for small arrays, but it becomes exponential and impractical for arrays close to length 16.

How does bitmasking help in this problem?

Bitmasking efficiently encodes used elements, allowing memoization of subset states and avoiding recomputation during recursion.

What is the significance of checking total sum divisibility by k?

If the total sum is not divisible by k, no equal-sum partition is possible, so early termination saves unnecessary computation.

Are repeated numbers handled differently?

No special handling is required, but tracking used elements carefully ensures each number is counted once per subset assignment.

terminal

Solution

Solution 1: DFS + Pruning

According to the problem description, we need to partition the array $\textit{nums}$ into $k$ subsets such that the sum of each subset is equal. Therefore, we first sum all the elements in $\textit{nums}$. If the total sum cannot be divided by $k$, it means we cannot partition the array into $k$ subsets, and we return $\textit{false}$ early.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        def dfs(i: int) -> bool:
            if i == len(nums):
                return True
            for j in range(k):
                if j and cur[j] == cur[j - 1]:
                    continue
                cur[j] += nums[i]
                if cur[j] <= s and dfs(i + 1):
                    return True
                cur[j] -= nums[i]
            return False

        s, mod = divmod(sum(nums), k)
        if mod:
            return False
        cur = [0] * k
        nums.sort(reverse=True)
        return dfs(0)

Solution 2: State Compression + Memoization

Similar to Solution 1, we first check whether the array $\textit{nums}$ can be partitioned into $k$ subsets. If it cannot be divided by $k$, we directly return $\textit{false}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        def dfs(i: int) -> bool:
            if i == len(nums):
                return True
            for j in range(k):
                if j and cur[j] == cur[j - 1]:
                    continue
                cur[j] += nums[i]
                if cur[j] <= s and dfs(i + 1):
                    return True
                cur[j] -= nums[i]
            return False

        s, mod = divmod(sum(nums), k)
        if mod:
            return False
        cur = [0] * k
        nums.sort(reverse=True)
        return dfs(0)

Solution 3: Dynamic Programming

We can use dynamic programming to solve this problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        def dfs(i: int) -> bool:
            if i == len(nums):
                return True
            for j in range(k):
                if j and cur[j] == cur[j - 1]:
                    continue
                cur[j] += nums[i]
                if cur[j] <= s and dfs(i + 1):
                    return True
                cur[j] -= nums[i]
            return False

        s, mod = divmod(sum(nums), k)
        if mod:
            return False
        cur = [0] * k
        nums.sort(reverse=True)
        return dfs(0)

Continue Practicing

#691 stickers to spell word #638 shopping offers #526 beautiful arrangement