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 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

2. 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

3. What is the worst-case time complexity of the optimized dynamic programming solution for the Largest Divisible Subset problem, where n is the number of elements in the input array?

medium

A. O(n^2) due to nested loops checking divisibility pairs

B. O(2^n) because all subsets are considered

C. O(n^3) because of triple nested loops for subset checks

D. O(n log n) due to sorting and linear DP

Solution

1. Step 1: Identify main operations

   Sorting takes O(n log n). The DP uses two nested loops: outer loop over n elements, inner loop up to i elements.

2. Step 2: Analyze nested loops

   Each pair (i,j) is checked once, resulting in O(n^2) divisibility checks. Early break may speed up in practice but worst case remains O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP nested loops dominate complexity [OK]

Hint: DP nested loops -> O(n^2) worst case [OK]

Common Mistakes:

• Confusing sorting time as dominant (O(n log n))
• Assuming triple nested loops due to subset checks
• Thinking brute force complexity applies to DP

4. What is the time complexity of generating all subsets of an array of size n using bitmask enumeration, and why is the common misconception that it is O(2^n) incorrect?

medium

A. O(n^2) because we iterate over n elements twice

B. O(2^n) because there are 2^n subsets

C. O(n * 2^n) because each subset can have up to n elements and we build each subset by checking n bits

D. O(n) because we process each element once

Solution

1. Step 1: Count subsets and subset size

   There are 2^n subsets, and each subset can have up to n elements.

2. Step 2: Analyze bitmask enumeration cost

   For each of the 2^n masks, we check n bits to build the subset, resulting in O(n * 2^n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time depends on both number of subsets and subset size [OK]

Hint: Each subset requires O(n) to build, total O(n*2^n) [OK]

Common Mistakes:

• Ignoring subset size in complexity
• Assuming O(2^n) only
• Confusing with DP complexities

5. Suppose you want to generate all combinations of size k from numbers 1 to n, but now elements can be reused multiple times in a combination (combinations with replacement). Which modification to the backtracking approach correctly handles this?

hard

A. Use iterative lexicographic generation without any changes

B. Change the recursive call to backtrack(i + 1, path) to prevent reuse of elements

C. Change the recursive call to backtrack(i, path) to allow reuse of the current element

D. Sort the input array before backtracking to handle duplicates

Solution

1. Step 1: Understand combinations with replacement allow repeated elements

   To allow reuse, the recursive call must not increment start index beyond current element.

2. Step 2: Modify recursion to backtrack(i, path) to allow current element reuse

   This ensures the same element can be chosen multiple times in subsequent recursive calls.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Using backtrack(i, path) enables combinations with replacement [OK]

Hint: Reuse requires recursive calls with same start index [OK]

Common Mistakes:

• Incrementing start index prevents element reuse