Bird
Raised Fist0

What is the return value when called with nums = [1, 2, 3, 4] and k = 2?

easy🧾 Code Trace Q12 of Q15
Dynamic Programming: Knapsack - Partition to K Equal Sum Subsets
Consider the following Python function implementing the DP with bitmask tabulation approach for partitioning an array into k equal sum subsets. What is the return value when called with nums = [1, 2, 3, 4] and k = 2?
from typing import List

def canPartitionKSubsets(nums: List[int], k: int) -> bool:
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort()
    if nums[-1] > target:
        return False

    dp = [-1] * (1 << n)
    dp[0] = 0

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

    return dp[(1 << n) - 1] == 0
ATrue
BFalse
CRaises an exception due to index error
DReturns None
Step-by-Step Solution
  1. Step 1: Calculate total and target

    Sum is 10, k=2, target subset sum = 5.
  2. Step 2: Trace dp updates

    DP explores subsets; for example, {1,4} and {2,3} both sum to 5, so dp[(1<<4)-1] = 0, returning True.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Partition exists: [1,4] and [2,3] [OK]
Quick Trick: Sum divisible by k and dp final state 0 means partition possible [OK]
Common Mistakes:
MISTAKES
  • Confusing dp array indexing or bitmask operations
  • Forgetting to check if largest element exceeds target
Trap Explanation:
PITFALL
  • Candidates often misinterpret dp array meaning or off-by-one bitmask errors.
Interviewer Note:
CONTEXT
  • Tests ability to mentally execute bitmask DP and understand final dp state meaning.
Master "Partition to K Equal Sum Subsets" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Dynamic Programming: Knapsack Quizzes