Partition to K Equal Sum Subsets

📋

Partition to K Equal Sum Subsets

Edge cases:

</>

IDE

def canPartitionKSubsets(nums: list[int], k: int) -> bool:public boolean canPartitionKSubsets(int[] nums, int k)bool canPartitionKSubsets(std::vector<int>& nums, int k)function canPartitionKSubsets(nums, k)

def canPartitionKSubsets(nums, k):
    # Write your solution here
    pass

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool canPartitionKSubsets(vector<int>& nums, int k) {
    // Write your solution here
    return false;
}

function canPartitionKSubsets(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueReturning true without checking if total sum is divisible by k.✅ Add a condition: if sum(nums) % k != 0: return false before backtracking.

Wrong: falseIncorrect backtracking pruning or missing base case for k=1.✅ Return true immediately if k == 1; ensure backtracking explores all valid assignments.

Wrong: trueReusing elements multiple times, confusing 0/1 with unbounded knapsack.✅ Track used elements with a visited array or bitmask to prevent reuse.

Wrong: falseGreedy approach assigning largest elements first without backtracking.✅ Implement full backtracking with pruning and try all bucket assignments.

Wrong: TLENaive exponential backtracking without memoization or pruning.✅ Use memoization or bitmask DP to cache states and prune early.

✓

Test Cases

Focus on handling empty arrays, single elements, and exact boundary conditions carefully.

Watch out for greedy traps and ensure correct element usage constraints.

Optimize your solution with memoization or bitmask DP to pass performance tests.

t1_01basic

Input{"nums":[4,3,2,3,5,2,1],"k":4}

Expectedtrue

⏱ Performance - must finish in 2000ms

We can partition into (5), (1,4), (2,3), (2,3) each summing to 5.

💡 Think about dividing the array into k subsets with equal sums.

💡 Check if total sum is divisible by k and use backtracking to assign elements.

💡 Sort nums descending and try placing each number into buckets without exceeding target sum.

Why it failed: Returned false or incorrect result: likely missed checking sum divisibility or incorrect backtracking pruning. Fix by verifying total sum % k == 0 and properly backtracking with bucket sums.

✓ Correctly partitions the array into k equal sum subsets.

t1_02basic

Input{"nums":[2,2,2,2,3,4,5],"k":4}

Expectedfalse

⏱ Performance - must finish in 2000ms

Total sum is 20, which is not divisible by 4, so partitioning is impossible.

💡 Start by checking if total sum is divisible by k.

💡 If not divisible, return false immediately without further checks.

💡 Implement an early exit condition for sum % k != 0.

Why it failed: Returned true despite sum not divisible by k: missing early sum divisibility check. Fix by adding total sum % k == 0 condition before backtracking.

✓ Correctly identifies impossible partition due to sum divisibility.

t2_01edge

Input{"nums":[],"k":1}

Expectedfalse

⏱ Performance - must finish in 2000ms

Empty array cannot form any non-empty subsets, so return false.

💡 Consider what happens if nums is empty.

💡 Check if input length is zero and handle as a base case.

💡 Return false if nums is empty since no subsets can be formed.

Why it failed: Returned true or error on empty input: missing base case for empty array. Fix by returning false if nums is empty.

✓ Correctly handles empty input by returning false.

t2_02edge

Input{"nums":[10],"k":1}

Expectedtrue

⏱ Performance - must finish in 2000ms

With k=1, the entire array is one subset, so always true.

💡 When k=1, the entire array is the subset.

💡 Check if k equals 1 and return true immediately.

💡 Add a condition to return true if k == 1 regardless of nums.

Why it failed: Returned false for k=1: missing shortcut for k=1 case. Fix by returning true immediately when k == 1.

✓ Correctly returns true when k=1.

t2_03edge

Input{"nums":[5,5,5,5],"k":2}

Expectedtrue

⏱ Performance - must finish in 2000ms

All elements equal; can partition into two subsets each summing to 10.

💡 If all elements are equal, partitioning is straightforward.

💡 Check if sum is divisible by k and all elements equal target/k.

💡 Return true if all elements equal and sum divisible by k.

Why it failed: Returned false despite all equal elements: missing handling for identical elements. Fix by ensuring backtracking tries equal elements correctly.

✓ Correctly partitions array with all equal elements.

t2_04edge

Input{"nums":[10000,10000,10000,10000],"k":2}

Expectedtrue

⏱ Performance - must finish in 2000ms

Large numbers test efficiency and pruning; partition into two subsets each summing to 20000.

💡 Large numbers require efficient pruning in backtracking.

💡 Sort descending and prune early when bucket sums exceed target.

💡 Use memoization or bitmask to avoid redundant states.

Why it failed: Returned false or TLE due to inefficient pruning with large numbers. Fix by sorting and pruning early in backtracking.

✓ Efficient pruning handles large numbers correctly.

t3_01corner

Input{"nums":[1,1,1,1,2,2,2,2],"k":4}

Expectedtrue

⏱ Performance - must finish in 2000ms

Greedy approach fails if it assigns large numbers first without backtracking; correct backtracking finds valid partition.

💡 Greedy assignment of largest elements first can fail.

💡 Use backtracking with pruning instead of greedy to explore all assignments.

💡 Sort descending and try all bucket placements with backtracking to avoid greedy traps.

Why it failed: Returned false due to greedy trap: assigning large elements first without backtracking. Fix by implementing full backtracking with pruning.

✓ Backtracking correctly finds valid partition avoiding greedy trap.

t3_02corner

Input{"nums":[2,2,2,2,2,2],"k":3}

Expectedtrue

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded knapsack: each element can be used once only.

💡 Each element can only be used once, not unlimited times.

💡 Track used elements with a visited array or bitmask.

💡 Ensure no element is assigned to more than one subset.

Why it failed: Returned true incorrectly by reusing elements multiple times: 0/1 vs unbounded confusion. Fix by marking elements used and disallow reuse.

✓ Correctly enforces 0/1 usage of elements.

t3_03corner

Input{"nums":[1,2,3,4,5,6,7],"k":3}

Expectedtrue

⏱ Performance - must finish in 2000ms

Off-by-one error in recursion index or bucket assignment can cause incorrect false negatives.

💡 Check recursion base case carefully for index == len(nums).

💡 Ensure all buckets sum to target at recursion end.

💡 Verify bucket sums updated and reverted correctly during backtracking.

Why it failed: Returned false due to off-by-one error in recursion or bucket sum checks. Fix by correcting base case and backtracking logic.

✓ Correct recursion and bucket sum management yields correct result.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],"k":4}

Expectednull

⏱ Performance - must finish in 2000ms

n=16, O(n*2^n) complexity must complete in 2s.

💡 Use memoization or bitmask DP to avoid exponential backtracking.

💡 Prune branches early when bucket sums exceed target.

💡 Avoid redundant state exploration with caching.

Why it failed: TLE due to naive exponential backtracking without memoization or pruning. Fix by implementing bitmask DP or memoized backtracking.

✓ Efficient DP or memoized backtracking completes within time limit.

Practice

1. Consider the following Python code implementing the space-optimized 0/1 Knapsack solution. What is the output when weights = [10, 20, 30], values = [60, 100, 120], and W = 50?

def knapsack_space_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
print(knapsack_space_optimized(weights, values, W))

easy

A. 240

B. 180

C. 160

D. 220

Solution

1. Step 1: Trace dp array updates for each item

   For item 0 (weight=10, value=60), dp[w] updated for w=50 down to 10, dp[10..50]=60. For item 1 (weight=20, value=100), dp[30]=max(dp[30], dp[10]+100)=160, dp[50]=max(dp[50], dp[30]+100)=220. For item 2 (weight=30, value=120), dp[50]=max(dp[50], dp[20]+120)=max(220, 160+120)=280 but dp[20] is 60, so dp[50]=max(220, 180)=220.

2. Step 2: Final dp[50] value

   The maximum value achievable with capacity 50 is 220.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Manual dp tracing confirms max value 220 [OK]

Hint: Trace dp updates backward to avoid overcounting [OK]

Common Mistakes:

• Forwards iteration over w causes overcounting items.

2. Consider the following code for computing the minimum number of perfect squares summing to n. What is the value of dp[4] after the outer loop iteration i = 4 completes?

easy

A. 4

B. 1

C. 3

D. 2

Solution

1. Step 1: Trace dp[4] updates

   For i=4, j iterates over 1 and 2 because 1*1=1 <=4 and 2*2=4 <=4. - For j=1: dp[4] = min(inf, 1 + dp[3]) = 1 + dp[3] - For j=2: dp[4] = min(previous, 1 + dp[0]) = min(previous, 1 + 0) = 1 Since dp[0] = 0, dp[4] becomes 1.

2. Step 2: Confirm dp[4] final value

   dp[4] = 1 means 4 can be represented as one perfect square (2*2). This matches the expected minimal count.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   dp[4] = 1 for 4 = 2^2 [OK]

Hint: dp[4] = 1 because 4 is a perfect square itself [OK]

Common Mistakes:

• Off-by-one errors in loop
• Ignoring dp[0] base case

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

4. The following code attempts to solve the Target Sum problem using bottom-up DP with offset indexing. Which line contains a subtle bug that causes incorrect results on inputs containing zero?

medium

A. Line 12-15: Updating dp array in-place instead of using a separate next_dp

B. Line 6: dp[offset] = 1

C. Line 10: if dp[s] != 0:

D. Line 8: for num in nums:

Solution

1. Step 1: Identify DP update method

   The code updates dp in-place during iteration over sums, causing double counting when num=0 or overlapping states.

2. Step 2: Understand impact on zero values

   Zero does not change sum, so updating dp in-place doubles counts incorrectly. Using a separate next_dp array avoids this.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   In-place updates cause state reuse within iteration, breaking correctness [OK]

Hint: In-place dp updates cause double counting with zero values [OK]

Common Mistakes:

• Not using a separate dp array for next iteration

5. Suppose the problem is modified so that you want to find the minimum number of perfect squares summing to n, but now each perfect square can only be used at most once. Which of the following changes correctly adapts the algorithm?

hard

A. Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse

B. Use a top-down memoized recursion with a visited set to avoid reusing squares

C. Use a 2D DP array where dp[i][j] represents minimum squares using first j squares to sum to i

D. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly

Solution

1. Step 1: Understand the constraint change

   Limiting each perfect square to be used at most once converts the problem from unbounded to 0/1 knapsack variant, requiring tracking which squares are used.

2. Step 2: Identify correct DP adaptation

   A 2D DP array dp[i][j] that tracks minimum squares to sum to i using first j squares correctly models the usage constraint. Other options either do not prevent reuse or do not track usage properly.

3. Step 3: Confirm why other options fail

   Keep the same bottom-up DP but iterate squares in increasing order and update dp[i] from dp[i - square] without reuse still allows reuse implicitly. Use a top-down memoized recursion with a visited set to avoid reusing squares is inefficient and complex. Change the inner loop to iterate over squares in decreasing order and update dp[i] accordingly's order change alone doesn't enforce usage limits.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   0/1 knapsack requires 2D DP to track usage [OK]

Hint: At-most-once usage -> 0/1 knapsack -> 2D DP needed [OK]

Common Mistakes:

• Trying to reuse unbounded DP
• Ignoring usage constraints in DP state