Partition to K Equal Sum Subsets

▶

Steps

setup

Calculate total sum and target per bucket

Calculate the total sum of nums and determine the target sum each bucket must reach by dividing total by k.

💡 Knowing the target sum is essential because the problem reduces to checking if subsets can sum exactly to this target.

Line:

total = sum(nums)
if total % k != 0:
    return False
target = total // k

💡 The problem is only solvable if total sum is divisible by k; otherwise, partitioning is impossible.

setup

Sort nums and check largest element against target

Sort the nums array to facilitate early pruning and check if the largest element exceeds the target sum.

💡 If any element is larger than the target, partitioning is impossible because that element alone can't fit in any bucket.

Line:

nums.sort()
if nums[-1] > target:
    return False

💡 Sorting helps in efficient DP traversal and pruning impossible cases early.

setup

Initialize dp array with -1 and set dp[0] = 0

Create a dp array of size 2^n initialized to -1, representing unreachable subsets, and mark the empty subset as reachable with sum 0.

💡 dp[mask] stores the current sum modulo target for the subset represented by mask; -1 means unreachable.

Line:

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

💡 Starting with the empty subset reachable with sum 0 sets the base case for DP.

fill_cells

Start iterating over all subset masks

Begin iterating over all subset masks from 0 to 2^n - 1 to explore reachable subsets.

💡 Each mask represents a subset of elements; we will try to add new elements to these subsets.

Line:

for mask in range(1 << n):
    if dp[mask] == -1:
        continue

💡 Only subsets marked reachable (dp[mask] != -1) can be expanded further.

fill_cells

Try adding element 6 (value 1) to empty subset

Check if element at index 6 (value 1) can be added to the empty subset without exceeding target.

💡 Adding elements to subsets builds new subsets; we only add if sum stays within target.

Line:

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

💡 We can form subset {1} with sum 1 mod 5 = 1.

fill_cells

Try adding element 2 (value 2) to empty subset

Check if element at index 2 (value 2) can be added to the empty subset without exceeding target.

💡 We explore all elements to build all possible subsets.

Line:

if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:

💡 Subset {2} with mask 4 (binary 0000100) is reachable with sum 2.

fill_cells

Try adding element 1 (value 2) to empty subset

Check if element at index 1 (value 2) can be added to the empty subset without exceeding target.

💡 Repeated values are handled similarly, expanding reachable subsets.

Line:

if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:

💡 Subset {2} with mask 2 (binary 0000010) is reachable with sum 2.

fill_cells

Try adding element 4 (value 4) to empty subset

Check if element at index 4 (value 4) can be added to the empty subset without exceeding target.

💡 Adding elements close to target tests boundary conditions.

Line:

if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:

💡 Subset {4} with mask 16 (binary 0010000) is reachable with sum 4.

fill_cells

Try adding element 3 (value 3) to empty subset

Check if element at index 3 (value 3) can be added to the empty subset without exceeding target.

💡 Adding larger elements expands subsets with higher sums.

Line:

if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:

💡 Subset {3} with mask 8 (binary 0001000) is reachable with sum 3.

fill_cells

Try adding element 5 (value 3) to empty subset

Check if element at index 5 (value 3) can be added to the empty subset without exceeding target.

💡 Repeated values again expand reachable subsets.

Line:

if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:

💡 Subset {5} with mask 32 (binary 0100000) is reachable with sum 3.

fill_cells

Try adding element 0 (value 4) to empty subset

Check if element at index 0 (value 4) can be added to the empty subset without exceeding target.

💡 Last element added to build initial reachable subsets.

Line:

if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:

💡 Subset {0} with mask 1 (binary 0000001) is reachable with sum 4.

fill_cells

Expand subsets by adding element 6 to subset {0}

From subset mask 1 (element 0), try adding element 6 (value 1) if sum does not exceed target.

💡 We build larger subsets by adding elements to reachable smaller subsets.

Line:

if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:

💡 Subset {0,6} with mask 65 is reachable with sum (4+1)%5=0.

fill_cells

Expand subsets by adding element 1 to subset {0}

From subset mask 1, try adding element 1 (value 2) if sum does not exceed target.

💡 Adding different elements to same subset explores all combinations.

Line:

if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:

💡 Cannot add element 1 to subset {0} as sum would exceed target.

fill_cells

Continue expanding subsets until full mask reachable

Iterate through all masks and elements, updating dp for reachable subsets by adding elements without exceeding target.

💡 This systematic expansion explores all subset combinations efficiently.

Line:

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

💡 The DP table eventually marks the full set mask reachable with sum 0 mod target, meaning partitioning is possible.

compare

Check final dp value for full mask

Check dp value for mask with all elements included to determine if partitioning is possible.

💡 If dp for full mask is 0, it means all elements can be partitioned into k subsets with equal sum.

Line:

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

💡 The full set is reachable with sum modulo target 0, confirming valid partitioning.

from typing import List

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

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

    for mask in range(1 << n):  # STEP 4, 14
        if dp[mask] == -1:
            continue
        for i in range(n):  # STEP 5-13
            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  # STEP 15

📊

Partition to K Equal Sum Subsets - Watch the Algorithm Execute, Step by Step

Watching this visualization helps you understand how bitmask DP explores all subsets efficiently and how the modulo operation tracks partial sums for equal partitions.

Initializing dp array

i\w

Initializing dp array

i\w

Initializing dp array

i\w	0
i=0	0

dp[0] = 0 (empty subset)

Initializing dp array

i\w	0
i=0	0

Current mask = 0 (empty subset)

Item 6 - wt:1 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63	64	65
i=0	0	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	1

mask=0 (empty subset)

Item 2 - wt:2 val:2

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63	64	65
i=0	0	?	?	?	2	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?

mask=0 (empty subset)

Item 1 - wt:2 val:2

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63	64
i=0	0	?	2	?	2	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?

mask=0 (empty subset)

Item 4 - wt:4 val:4

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63
i=0	0	?	2	?	2	?	?	?	?	?	?	?	?	?	?	?	4	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?

mask=0 (empty subset)

Item 3 - wt:3 val:3

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63
i=0	0	?	2	?	2	?	?	?	3	?	?	?	?	?	?	?	4	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?

mask=0 (empty subset)

Item 5 - wt:3 val:3

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59
i=0	0	?	2	?	2	?	?	?	3	?	?	?	?	?	?	?	4	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	3	?	?	?	?	?	?	?	?	?	?	?

mask=0 (empty subset)

Item 0 - wt:4 val:4

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59
i=0	0	4	2	?	2	?	?	?	3	?	?	?	?	?	?	?	4	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	3	?	?	?	?	?	?	?	?	?	?	?

mask=0 (empty subset)

Item 6 - wt:1 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59
i=0	0	4	2	?	2	?	?	?	3	?	?	?	?	?	?	?	4	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	3	?	?	?	?	?	?	?	?	?	?	0

mask=1 (subset {0})

Item 1 - wt:2 val:2

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59
i=0	0	4	2	?	2	?	?	?	3	?	?	?	?	?	?	?	4	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	?	3	?	?	?	?	?	?	?	?	?	?	0

mask=1 (subset {0})

Initializing dp array

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63	64	65	66	67	68	69	70	71
i=0	0	4	2	3	2	3	4	0	3	4	0	1	1	2	3	4	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4

DP table partially filled

Initializing dp array

i\w	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63	64	65	66	67	68	69	70
i=0	0	4	2	3	2	3	4	0	3	4	0	1	1	2	3	4	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	3	4	0	1	2	0

Answer cell dp[127] = 0 (partition possible)

Key Takeaways

✓ Bitmask DP efficiently explores all subsets by representing them as integers and tracking partial sums modulo target.

This insight is hard to see from code alone because the bitmask representation and modulo arithmetic are abstract concepts.

✓ The DP table's fill order depends on reachable subsets, ensuring no redundant computations and pruning unreachable states.

Visualizing the fill order clarifies why some subsets are never reached and how the algorithm avoids unnecessary work.

✓ The final decision depends on whether the full set mask is reachable with sum modulo target zero, confirming equal partitioning.

Seeing the final dp cell highlighted as the answer cell concretely connects the DP state to the problem's solution.

Practice

1. You are given a list of positive integers and need to determine if it can be split into two subsets with equal sums. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming using a subset-sum style 0/1 knapsack approach to check for a subset with sum equal to half the total

B. Divide and conquer by recursively splitting the array into halves and checking sums

C. Sorting the array and using two pointers to find two subsets with equal sums

D. Greedy algorithm that picks the largest elements first until half the total sum is reached

Solution

1. Step 1: Understand the problem requires partitioning into two equal sum subsets

   Since the problem asks if the array can be split into two subsets with equal sums, it reduces to finding a subset with sum equal to half the total sum.

2. Step 2: Identify the algorithm that checks subset sums efficiently

   The 0/1 knapsack dynamic programming approach can determine if such a subset exists by building a DP table or array that tracks achievable sums up to half the total.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy and sorting approaches fail on many inputs; DP guarantees correctness [OK]

Hint: Partition reduces to subset sum with half total [OK]

Common Mistakes:

• Thinking greedy or sorting solves partition optimally

2. What is the time complexity of the space-optimized bottom-up 0/1 Knapsack algorithm when there are n items and the knapsack capacity is W?

medium

A. O(2^n)

B. O(n + W)

C. O(n * W)

D. O(n * log W)

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm has an outer loop over n items and an inner loop over capacities from W down to the item's weight, which can be up to W iterations.

2. Step 2: Calculate total operations

   Multiplying the loops gives O(n * W) time complexity. Recursive brute force is exponential, and linear or logarithmic complexities are incorrect here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops over n and W -> O(n * W) [OK]

Hint: Nested loops over items and capacity -> O(n * W) [OK]

Common Mistakes:

• Confusing recursion stack space with time complexity.

3. The following code attempts to count the number of combinations to make change. Which line contains a subtle bug that causes it to count permutations instead of combinations?

medium

A. Line 5: inner loop iterating backwards over amounts

B. Line 4: outer loop over coins

C. Line 2: dp initialization

D. Line 6: updating dp[w] with dp[w - coin]

Solution

1. Step 1: Understand iteration order effect

   Iterating amounts backwards causes dp to count permutations, not combinations.

2. Step 2: Identify bug line

   Line 5 iterates w from amount down to coin, which breaks combination counting logic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration over amounts is required to count combinations correctly [OK]

Hint: Check direction of inner loop iteration [OK]

Common Mistakes:

• Using backward iteration in 1D dp
• Misplacing dp[0] initialization

4. The following code attempts to solve the coin change minimum coins problem. Identify the line containing the subtle bug that causes incorrect results or infinite recursion for amount=0.

def coinChange(coins, amount):
    def dfs(rem):
        if rem == 0:
            return 0
        res = float('inf')
        for coin in coins:
            if rem - coin >= 0:
                res = min(res, 1 + dfs(rem - coin))
        return res
    ans = dfs(amount)
    return ans if ans != float('inf') else -1

medium

A. Line 3: Missing base case for rem < 0

B. Line 6: Missing check for rem == 0 before recursion

C. Line 9: Returning res without checking if res is still infinity

D. Line 7: Incorrect condition rem - coin >= 0 instead of rem >= coin

Solution

1. Step 1: Analyze base cases in recursion

   Code handles rem == 0 but lacks base case for rem < 0, but since rem - coin >= 0 check prevents negative rem, no infinite recursion occurs.

2. Step 2: Check return value correctness

   Returning res directly without checking if res is still infinity can cause incorrect results when no valid coin combination exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Must check if res is infinity before returning to handle no solution cases correctly [OK]

Hint: Check if result is infinity before returning in recursion [OK]

Common Mistakes:

• Forgetting to handle no solution case
• Assuming rem == 0 base case suffices

5. Suppose the problem is modified so that each coin can be used at most once (0/1 knapsack variant). Which of the following changes to the original code correctly counts the number of combinations?

hard

A. Change inner loop to iterate amounts backward (from amount down to coin) to avoid reuse

B. Change inner loop to iterate amounts forward (from coin to amount) as in original code

C. Use recursion without memoization to explore all subsets

D. Use greedy approach picking largest coins first

Solution

1. Step 1: Understand 0/1 knapsack constraints

   Each coin can be used once, so dp updates must avoid reuse within same iteration.

2. Step 2: Identify correct iteration order

   Iterating amounts backward ensures dp[w] uses dp[w - coin] from previous iteration, preventing reuse.

3. Step 3: Evaluate other options

   Forward iteration allows reuse; recursion without memoization is inefficient; greedy is incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backward iteration is standard for 0/1 knapsack to avoid reuse [OK]

Hint: Backward iteration prevents reuse in 0/1 knapsack [OK]

Common Mistakes:

• Using forward iteration causing reuse
• Relying on greedy or naive recursion