Partition to K Equal Sum Subsets

Medium · Backtracking · Explanation and code example

Dynamic Programming (Bottom-Up) + Bit Mask

How it works

Instead of recursion, we iterate through all possible mask values from 0 to 2^n - 1. For each valid state (reachable configuration), we try adding each unused element. The key insight is that dp[mask] stores the current sum modulo target. If we can reach the full mask with sum 0 (meaning all subsets are complete), we have a valid partition.

Steps

  1. Calculate the total sum. If it's not divisible by k, return false.
  2. Compute target = total / k.
  3. Initialize dp array of size 2^n with -1, except dp[0] = 0.
  4. For each mask from 0 to 2^n - 1:
    • If dp[mask] == -1, this state is unreachable; skip it.
    • For each element i:
      • If bit i is not set and adding nums[i] doesn't exceed target:
        • Set dp[mask | (1 << i)] = (dp[mask] + nums[i]) % target.
  5. Return true if dp[(1 << n) - 1] == 0, meaning all elements are used and the sum completes exactly.

Complexity

  • Time complexity: O(n * 2 ^ n)
  • Space complexity: O(2 ^ n)

Python code example

from typing import List

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total = sum(nums)
        if total % k != 0:
            return False

        target = total // k
        n = len(nums)
        N = 1 << n
        dp = [0] + [-1] * (N - 1)

        for mask in range(N):
            if dp[mask] == -1:
                continue
            for i in range(n):
                if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
                    dp[mask | (1 << i)] = (dp[mask] + nums[i]) % target

        return dp[N - 1] == 0

C++ code example

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % k != 0) return false;

        int target = total / k;
        int n = nums.size();
        int N = 1 << n;
        vector<int> dp(N, -1);
        dp[0] = 0;

        for (int mask = 0; mask < N; mask++) {
            if (dp[mask] == -1) continue;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0 && dp[mask] + nums[i] <= target) {
                    dp[mask | (1 << i)] = (dp[mask] + nums[i]) % target;
                }
            }
        }

        return dp[N - 1] == 0;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations