Skip to main content

698. Partition to K Equal Sum Subsets

medium

Decide if you can partition an array into k subsets with equal sum. Bitmask DP over which elements have been used — a textbook subset-sum variant.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Constraints

  • 1 <= k <= nums.length <= 16
  • 1 <= nums[i] <= 10^4
  • 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: Subsets (5), (1,4), (2,3), (2,3) all sum to 5.

Example 2

Input
nums = [1,2,3,4], k = 3
Output
false

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Target subset sum = total / k. If total % k != 0 or max(nums) > target, return false.

Hint 2

Bitmask DP: dp[mask] = remainder of the current bucket's sum modulo target when elements in mask have been used.

Hint 3

Transition: from state mask try adding element i (bit i unset) if dp[mask] + nums[i] <= target. Answer = dp[fullMask] == 0.

Solution approach

Reveal approach

Bitmask DP over the set of used elements. Compute target = total / k; early exit if total is not divisible or any element exceeds target. Define the subproblem dp[mask] = the running sum modulo target of the bucket currently being filled when the items indicated by mask have already been placed (-1 if mask is unreachable). The recurrence relation: from a reachable mask with value v, try every bit i not set in mask such that v + nums[i] <= target. The new mask' = mask | (1 << i) is reachable with value (v + nums[i]) % target — the modulo trick automatically closes a bucket the moment it hits exactly target, starting a new one with running sum 0. Initialize dp[0] = 0 and mark others unreachable. Process masks in increasing popcount order. The answer is dp[(1 << n) - 1] == 0 (final mask reachable with no open bucket). Time O(n * 2^n), space O(2^n). For n <= 16 this fits comfortably.

Complexity

Time
O(n * 2^n)
Space
O(2^n)

Related patterns

  • dynamic-programming
  • memoization-recursion
  • bitmask-dp
  • subset-sum

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Partition to K Equal Sum Subsets and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →