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 optimal backtracking with bitmask and memoization approach for the Matchsticks to Square problem. Given the input [1,1,2,2,2], what is the final return value of makesquare([1,1,2,2,2])?

easy

A. True

B. Depends on the order of matchsticks

C. Raises an exception due to index error

D. False

Solution

1. Step 1: Calculate total and side length

   Total = 1+1+2+2+2 = 8, side = 8/4 = 2.

2. Step 2: Trace backtracking calls

   Sorted sticks: [2,2,2,1,1]. The algorithm tries to form sides of length 2. It can form three sides with three 2's, and the last side with two 1's. Hence, returns true.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum divisible by 4 and sticks fit sides exactly [OK]

Hint: Sum divisible by 4 and sticks fit sides exactly [OK]

Common Mistakes:

• Forgetting to sort and prune
• Assuming order affects result
• Miscounting sides formed

2. Consider the following code snippet implementing the trie-based solution for counting valid words for puzzles. Given the words = ["apple", "plea", "plead"] and puzzles = ["aelwxyz"], what is the returned count for this puzzle?

easy

A. [1]

B. [0]

C. [2]

D. [3]

Solution

1. Step 1: Compute bitmasks for words

   "apple" -> letters {a,p,l,e}, mask with ≤7 bits; "plea" and "plead" similarly processed.

2. Step 2: Check puzzle "aelwxyz"

   First letter 'a' must be in word; words "apple" and "plea" contain 'a' and are subsets of puzzle letters; "plead" contains 'd' not in puzzle.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two words match conditions [OK]

Hint: Count words containing puzzle first letter and subset of puzzle letters [OK]

Common Mistakes:

• Counting words missing first letter
• Including words with letters outside puzzle
• Off-by-one in counting matches

3. Consider the following Python code for generating subsets with duplicates. What is the value of res after processing the input [1, 2, 2]?

easy

A. [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]

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

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

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

Solution

1. Step 1: Trace iterations for input [1, 2, 2]

   Start with res = [[]]. - i=0 (num=1): s=0, start=1, add [1] -> res = [[], [1]] - i=1 (num=2): s=0, start=2, add [2], [1,2] -> res = [[], [1], [2], [1,2]] - i=2 (num=2): duplicate, s=start from previous iteration=2, start=4, add [2,2], [1,2,2] -> res = [[], [1], [2], [1,2], [2,2], [1,2,2]]

2. Step 2: Confirm final res matches option

   The final res contains exactly these subsets without duplicates: [], [1], [2], [1,2], [2,2], [1,2,2].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected unique subsets for input [1,2,2] [OK]

Hint: Duplicate skips start index to avoid repeats [OK]

Common Mistakes:

• Appending duplicates multiple times by resetting s=0 always
• Off-by-one errors in start index
• Including extra subsets from previous iterations

4. What is the worst-case time complexity of the optimal backtracking solution with sum bound pruning for Combination Sum III (k numbers from 1 to 9 summing to n)?

medium

A. O(k!) because permutations of k numbers are explored

B. O(k * n) because we explore all sums up to n for k elements

C. O(n^k) because we try all sequences of length k with sum n

D. O(2^9) because each number 1-9 can be either included or excluded, pruning reduces calls but worst case remains exponential

Solution

1. Step 1: Identify search space size

   Numbers 1 to 9 can be included or excluded, so 2^9 subsets possible.

2. Step 2: Consider pruning effect

   Pruning reduces calls but worst-case complexity remains O(2^9) since all subsets might be explored.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking worst case is exponential in number of candidates [OK]

Hint: Backtracking subsets of 9 elements is O(2^9) worst case [OK]

Common Mistakes:

• Confusing with DP complexity O(k*n)
• Thinking permutations cause factorial complexity

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