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

2. What is the time complexity of the iterative lexicographic combinations generation algorithm for generating all combinations of size k from n elements?

medium

A. O(n^k) because each element can be chosen or not

B. O(k * (n choose k)) since each combination of size k is generated once and updated in O(k)

C. O(\u03C3(n choose k) * k) where \u03C3 is the number of combinations generated

D. O(n * k) because the outer loop runs n times and inner loop k times

Solution

1. Step 1: Identify number of combinations

   There are exactly (n choose k) combinations to generate.

2. Step 2: Analyze per-combination cost

   Each combination is generated and updated in O(k) time due to copying and resetting elements.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time is proportional to number of combinations times combination size [OK]

Hint: Time depends on number of combinations times k [OK]

Common Mistakes:

• Confusing with exponential O(n^k) or linear O(n*k) complexities

3. The following code attempts to find the largest divisible subset but contains a subtle bug. Identify the line with the bug.

def largestDivisibleSubset(nums):
    if not nums:
        return []
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_index = 0

    for i in range(n):
        for j in range(i - 1, -1, -1):
            if nums[j] % nums[i] == 0:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            else:
                break
        if dp[i] > dp[max_index]:
            max_index = i

    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]

medium

A. Line with 'result.append(nums[max_index])'

B. Line with 'dp = [1] * n'

C. Line with 'max_index = 0'

D. Line with 'if nums[j] % nums[i] == 0:'

Solution

1. Step 1: Check divisibility condition

   The condition should be nums[i] % nums[j] == 0 because we want to check if current number is divisible by a smaller number.

2. Step 2: Understand impact of bug

   Using nums[j] % nums[i] == 0 reverses the divisibility logic, causing incorrect dp updates and wrong subsets.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct divisibility check is crucial for correctness [OK]

Hint: Divisibility check direction matters [OK]

Common Mistakes:

• Swapping divisor and dividend in modulo check
• Not sorting input before DP
• Incorrect subset reconstruction

4. Suppose the problem changes: now candidates can include negative numbers, and you still want all unique combinations summing to the target with reuse allowed. Which modification to the backtracking approach is necessary to handle this variant correctly?

hard

A. Remove pruning on target < 0 and add a visited set to detect cycles to avoid infinite recursion.

B. No change needed; the existing backtracking with pruning on target < 0 still works correctly.

C. Sort candidates in descending order and prune when target is less than the smallest candidate.

D. Use dynamic programming instead of backtracking because negative numbers break recursion.

Solution

1. Step 1: Understand impact of negative candidates

   Negative numbers allow sums to decrease indefinitely, causing infinite recursion if pruning on target < 0 is used or missing.

2. Step 2: Modify pruning and cycle detection

   Pruning on target < 0 is invalid because target can oscillate; must remove it and add a visited set or memoization to detect repeated states and avoid infinite loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detection is essential when negative numbers allow infinite recursion [OK]

Hint: Negative numbers require cycle detection to prevent infinite recursion [OK]

Common Mistakes:

• Assuming pruning on target < 0 always applies
• Ignoring infinite recursion caused by negatives

5. Suppose the problem is modified so that elements can be chosen multiple times (unlimited reuse) to form subsets. Which approach correctly adapts to count the number of max bitwise-OR subsets under this new constraint?

hard

A. Use dynamic programming over OR values with state compression to count combinations

B. Use backtracking with memoization to handle repeated elements and prune search

C. Use the same bitmask enumeration approach since subsets remain finite

D. Sort elements and greedily pick those with highest bits until max OR is reached

Solution

1. Step 1: Recognize infinite subsets due to unlimited reuse

   Bitmask enumeration is infeasible as subsets are infinite with reuse allowed.

2. Step 2: Use DP over OR states to count combinations efficiently

   DP with state compression tracks counts of subsets achieving each OR value, handling reuse.

3. Step 3: Understand greedy or naive backtracking fail due to infinite or redundant subsets

   Greedy misses combinations; naive backtracking is exponential and inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP over OR states handles reuse -> correct and efficient [OK]

Hint: Reuse means infinite subsets -> DP over OR states needed [OK]

Common Mistakes:

• Trying bitmask enumeration despite infinite subsets
• Using greedy approach ignoring subset counts