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. Consider the following Python code implementing the optimal backtracking solution for Combination Sum II. What is the final returned list when calling combinationSum2([1,2,2], 4)?

easy

A. [[1,2,2]]

B. [[1,2],[2]]

C. [[1,2],[2,2]]

D. [[1,2],[2,2],[1,2,2]]

Solution

1. Step 1: Sort candidates and start backtracking

   Sorted candidates: [1,2,2]. Start from index 0 with target=4.

2. Step 2: Explore combinations skipping duplicates at same level

   Try 1 -> target=3, then try 2 at next index -> target=1, next 2 is duplicate at same level skipped. No further candidates fit. Backtrack and try 2 at index 1 -> target=2, next 2 at index 2 -> target=0, add [2,2]. Both [1,2,2] and [2,2] are valid unique combinations.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both [1,2,2] and [2,2] sum to 4 without reuse and duplicates skipped [OK]

Hint: Duplicate skipping prevents repeated combinations [OK]

Common Mistakes:

• Including partial sums like [2]
• Allowing reuse of elements
• Not skipping duplicates at same recursion level

2. You are given a set of distinct positive integers and a target sum. You need to find all unique combinations where the chosen numbers sum to the target. Each number can be chosen multiple times. Which algorithmic approach best guarantees finding all valid combinations efficiently without missing any or producing duplicates?

easy

A. Greedy algorithm that picks the largest candidate repeatedly until the sum is reached or exceeded.

B. Backtracking with sorting and frequency counting to avoid duplicates and prune early when sum exceeds target.

C. Dynamic programming using a 2D table to count the number of combinations without generating them explicitly.

D. Pure brute force recursion that tries all subsets without pruning or sorting.

Solution

1. Step 1: Understand problem constraints

   The problem requires all unique combinations summing to target, allowing reuse of candidates.

2. Step 2: Evaluate algorithm suitability

   Greedy fails because it can miss combinations; pure brute force is correct but inefficient; DP counts combinations but doesn't generate them; backtracking with sorting and frequency counting avoids duplicates and prunes search space efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning and frequency counting is the standard approach [OK]

Hint: Backtracking with pruning avoids duplicates and excessive search [OK]

Common Mistakes:

• Assuming greedy always works for sum problems
• Confusing counting with generating combinations

3. The following code attempts to solve Combination Sum II but contains a subtle bug. Identify the line causing the bug.

medium

A. Line with 'if i > start and candidates[i] == candidates[i-1]: continue' for duplicate skipping

B. Line with 'if candidates[i] > target: break' for pruning

C. Line with 'backtrack(i + 1, path + [candidates[i]], target - candidates[i])' recursive call

D. Line with 'prev = candidates[i]' inside the loop

Solution

1. Step 1: Understand duplicate skipping logic

   The code uses 'if i > start and candidates[i] == candidates[i-1]: continue' to skip duplicates correctly.

2. Step 2: Identify subtle bug

   The 'prev' variable is assigned but never used, which is redundant and may confuse readers. The actual duplicate skipping is done by the index comparison, so 'prev' should be removed to avoid confusion.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Redundant 'prev' variable assignment is a subtle bug causing confusion [OK]

Hint: Duplicate skipping must be consistent and correct at recursion level; remove unused variables [OK]

Common Mistakes:

• Using prev variable incorrectly
• Skipping duplicates globally instead of per recursion level
• Not pruning when candidate > target

4. Identify the bug in the following code snippet for counting max bitwise-OR subsets:

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_or = 0
        count = 0
        for mask in range(0, 1 << n):  # Note: starts from 0
            current_or = 0
            for i in range(n):
                if mask & (1 << i):
                    current_or |= nums[i]
            if current_or > max_or:
                max_or = current_or
                count = 1
            elif current_or == max_or:
                count += 1
        return count

medium

A. The count variable should be reset inside the inner loop

B. The OR operation should be replaced with AND

C. The loop should start from 1 to exclude empty subset

D. max_or should be initialized to -1 instead of 0

Solution

1. Step 1: Identify that mask=0 represents empty subset

   Empty subset OR is 0, which is usually not counted as a valid subset.

2. Step 2: Recognize that including empty subset inflates count incorrectly

   Starting from mask=0 causes counting empty subset, leading to wrong final count.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Exclude empty subset by starting mask from 1 -> correct counting [OK]

Hint: Empty subset mask=0 must be excluded to avoid incorrect counts [OK]

Common Mistakes:

• Counting empty subset as valid
• Incorrect initialization of max_or

5. Suppose the problem is modified so that elements can be reused multiple times in the subset (i.e., the subset can contain duplicates). Which modification to the algorithm is necessary to correctly find the largest divisible subset under this new constraint?

hard

A. Modify DP to consider all previous elements including i itself, allowing repeated use, and remove early break

B. Switch to a graph cycle detection algorithm to handle repeated elements

C. Use the same DP approach but allow dp[i] to consider dp[i] itself for reuse, enabling cycles

D. Use a greedy approach picking the largest element repeatedly until no more divisible

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means elements can appear multiple times, so dp must consider extending from the same element multiple times.

2. Step 2: Modify DP logic

   DP inner loop must consider j ≤ i (including i itself) and remove early break because sorted order no longer guarantees divisibility breaks.

3. Step 3: Reject incorrect options

   Greedy fails to find longest chain; graph cycle detection is unnecessary; naive DP without modification misses reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP adjusted for reuse and no early break handles duplicates [OK]

Hint: Reuse requires DP to consider self and no early break [OK]

Common Mistakes:

• Using original DP without changes leads to incorrect results
• Trying greedy approach which fails on complex divisibility
• Confusing graph cycles with DP chains