Equal Partition (Partition Equal Subset Sum)

📋

Problem

Imagine you have a collection of weights and want to split them into two groups with exactly the same total weight. Can you do it?

Given a non-empty array of positive integers nums, determine if it can be partitioned into two subsets such that the sum of elements in both subsets is equal. Return true if such a partition exists, otherwise false.

1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 100

Edge cases: Single element array [1] → falseAll elements are the same [2, 2, 2, 2] → trueArray with one very large element and small others [100, 1, 1, 1] → false

</>

IDE

def canPartition(nums: list[int]) -> bool:public boolean canPartition(int[] nums)bool canPartition(vector<int>& nums)function canPartition(nums)

def canPartition(nums):
    # Write your solution here
    pass

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

#include <vector>
using namespace std;

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

function canPartition(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueReturning true for arrays with odd total sum because no early check for sum%2.✅ Add 'if sum(nums) % 2 != 0: return False' before DP.

Wrong: trueTreating problem as unbounded knapsack allowing multiple uses of elements.✅ Use 0/1 knapsack DP logic: for i in range(n): for w in reverse order.

Wrong: trueGreedy approach picking largest elements first without DP.✅ Replace greedy with boolean DP subset sum approach.

Wrong: trueIncorrect DP initialization or state transitions causing false positives.✅ Initialize dp[0] = True and update dp[w] = dp[w] or dp[w - nums[i]] carefully.

Wrong: crash or errorNo handling of empty input array causing index errors.✅ Add explicit check for empty input returning False.

✓

Test Cases

Focus on handling empty and minimal inputs correctly.

Avoid greedy and unbounded knapsack mistakes; enforce 0/1 constraints.

Optimize your DP to run efficiently on large inputs.

t1_01basic

Input{"nums":[1,5,11,5]}

Expectedtrue

⏱ Performance - must finish in 2000ms

The array can be partitioned as [1, 5, 5] and [11], both summing to 11.

💡 Think about splitting the array into two subsets with equal sum.

💡 Use dynamic programming to check if a subset sums to half the total sum.

💡 Implement a boolean DP to find if sum/2 is achievable from the elements.

Why it failed: Failed basic case: likely incorrect handling of subset sum target or DP state transitions. Fix by ensuring DP checks sums up to total//2 correctly.

✓ Correctly identifies partition possibility using subset sum DP.

t1_02basic

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

Expectedfalse

⏱ Performance - must finish in 2000ms

No partition exists because total sum is 11 (odd), so equal split impossible.

💡 Check if total sum is even before attempting partition.

💡 If sum is odd, return false immediately.

💡 Add a condition to handle odd total sums early to optimize.

Why it failed: Fails to detect odd total sum early, causing incorrect true output or wasted computation. Fix by adding sum%2 check before DP.

✓ Correctly returns false for arrays with odd total sum.

t2_01edge

Input{"nums":[]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty array cannot be partitioned into two equal subsets.

💡 Consider what happens when input array is empty.

💡 Check if your code handles n=0 without errors.

💡 Return false immediately if array is empty.

Why it failed: Fails on empty input by crashing or returning true. Fix by adding explicit check for empty array returning false.

✓ Handles empty input gracefully by returning false.

t2_02edge

Input{"nums":[1]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Single element array cannot be split into two equal sum subsets.

💡 Single element means total sum equals that element.

💡 Check if total sum is even and greater than zero.

💡 Return false if array length is 1 or sum is odd.

Why it failed: Incorrectly returns true for single element input. Fix by ensuring sum%2==0 and n>1 before DP.

✓ Correctly returns false for single element arrays.

t2_03edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

All elements identical and even count can be partitioned equally.

💡 Check if DP handles multiple identical elements correctly.

💡 Verify that subset sum DP does not double count elements.

💡 Ensure DP state transitions consider each element once.

Why it failed: Fails on identical elements by incorrect DP state updates or counting. Fix by using 0/1 knapsack logic, not unbounded.

✓ Correctly partitions arrays with identical elements.

t3_01corner

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Large element with small others cannot be partitioned equally.

💡 Check if your DP correctly handles large weights relative to target.

💡 Verify that DP does not allow multiple uses of the same element (0/1 constraint).

💡 Fix by ensuring each element is used at most once in DP transitions.

Why it failed: Fails due to treating problem as unbounded knapsack allowing multiple uses of elements. Fix by using 0/1 knapsack DP logic.

✓ Correctly enforces 0/1 usage of elements in DP.

t3_02corner

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Sum is odd (5), so partition impossible.

💡 Check if your code handles odd total sums correctly.

💡 Verify early return on odd sums before DP.

💡 Add sum%2 check before any DP computation.

Why it failed: Fails by attempting DP on odd sum arrays and returning incorrect true. Fix by adding early odd sum check.

✓ Correctly returns false for odd sum arrays.

t3_03corner

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

Expectedfalse

⏱ Performance - must finish in 2000ms

Greedy approach fails here; sum=8, half=4, but no subset sums to 4.

💡 Beware greedy picking largest elements first may fail.

💡 Use DP to explore all subset sums rather than greedy.

💡 Implement boolean DP to check all sums up to target.

Why it failed: Fails greedy trap by returning true incorrectly. Fix by replacing greedy with DP subset sum approach.

✓ Correctly rejects greedy trap cases using DP.

t4_01performance

Input{"nums":[100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, all elements 100, sum=10000, DP complexity O(n*sum/2)=O(100*5000)=500000 operations, must complete within 2s.

💡 DP complexity is O(n * target), where target = sum/2.

💡 Avoid exponential brute force; use bottom-up DP.

💡 Optimize space by using 1D DP array for subset sums.

Why it failed: TLE due to exponential brute force or inefficient recursion. Fix by implementing DP with O(n*target) complexity.

✓ Efficient DP solution runs within time limits.

Practice

1. The following code attempts to solve the coin change minimum coins problem. Identify the line containing the subtle bug that causes incorrect results or infinite recursion for amount=0.

def coinChange(coins, amount):
    def dfs(rem):
        if rem == 0:
            return 0
        res = float('inf')
        for coin in coins:
            if rem - coin >= 0:
                res = min(res, 1 + dfs(rem - coin))
        return res
    ans = dfs(amount)
    return ans if ans != float('inf') else -1

medium

A. Line 3: Missing base case for rem < 0

B. Line 6: Missing check for rem == 0 before recursion

C. Line 9: Returning res without checking if res is still infinity

D. Line 7: Incorrect condition rem - coin >= 0 instead of rem >= coin

Solution

1. Step 1: Analyze base cases in recursion

   Code handles rem == 0 but lacks base case for rem < 0, but since rem - coin >= 0 check prevents negative rem, no infinite recursion occurs.

2. Step 2: Check return value correctness

   Returning res directly without checking if res is still infinity can cause incorrect results when no valid coin combination exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Must check if res is infinity before returning to handle no solution cases correctly [OK]

Hint: Check if result is infinity before returning in recursion [OK]

Common Mistakes:

• Forgetting to handle no solution case
• Assuming rem == 0 base case suffices

2. What is the time complexity of the space-optimized bottom-up DP solution for Last Stone Weight II, where n is the number of stones and sum is the total weight of all stones?

medium

A. O(n + sum)

B. O(n^2)

C. O(n * sum * log n)

D. O(n * sum)

Solution

1. Step 1: Identify loops in the code

   Outer loop runs n times (for each stone), inner loop runs up to half the total sum (sum/2).

2. Step 2: Calculate total operations

   Each iteration updates dp array, so total operations ≈ n * (sum/2) -> O(n * sum).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP complexity depends on n and sum, not n squared or log factors [OK]

Hint: DP loops over stones and sums -> O(n * sum) [OK]

Common Mistakes:

• Confusing n with sum leading to O(n^2)
• Assuming logarithmic factor due to sorting
• Ignoring that dp array size depends on sum

3. The following code attempts to solve the job scheduling problem optimally. Which line contains a subtle bug that can cause incorrect results?

medium

A. Line 11: Using bisect_right to find compatible job index

B. Line 7: Creating ends array from job end times

C. Line 4: Sorting jobs by start time instead of end time

D. Line 14: Calculating dp[i] as max of take and skip

Solution

1. Step 1: Identify sorting criteria

   Jobs must be sorted by end time for binary search on ends array to work correctly.

2. Step 2: Check sorting line

   Line 4 sorts by start time, breaking DP dependencies and binary search correctness.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting by start time causes incorrect compatible job lookups and suboptimal profits [OK]

Hint: Sort jobs by end time, not start time [OK]

Common Mistakes:

• Sorting by start time
• Incorrect binary search bounds
• Ignoring dp base cases

4. What is the time complexity of the space-optimized bottom-up subset sum algorithm given an input list of size n and target sum S?

medium

A. O(2^n)

B. O(n + S)

C. O(n * S)

D. O(n * log S)

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm has an outer loop over n elements and an inner loop over sums from S down to each num.

2. Step 2: Calculate total operations

   Each element causes up to S iterations, so total time is O(n * S). Recursive brute force is exponential, and linear or log factors are incorrect.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops over n and S -> O(n * S) [OK]

Hint: Nested loops over n and S -> multiply complexities [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming linear or exponential time incorrectly

5. Suppose the integer break problem is modified so that you can reuse the same integer parts multiple times (unbounded splits), and you want to find the maximum product. Which modification to the DP approach below correctly handles this variant?

def integer_break(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        max_product = 0
        for j in range(1, i):
            max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
        dp[i] = max_product
    return dp[n]

Options:

hard

A. Use a nested loop where for each i, iterate j from 1 to i and update dp[i] = max(dp[i], j * dp[i-j]) to allow reuse

B. Sort possible parts and greedily pick the largest part repeatedly to maximize product

C. Keep the same code but add memoization to avoid recomputation

D. Change inner loop to iterate over all j ≤ i and update dp[i] as max(dp[i], dp[i-j] * dp[j]) without max(j, dp[j])

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means dp[i] depends on dp[i-j] multiplied by j (or dp[j]) where j can be reused multiple times.

2. Step 2: Modify DP update

   Updating dp[i] = max(dp[i], j * dp[i-j]) correctly models unbounded splits by combining current part j and best product for remaining i-j.

3. Step 3: Evaluate other options

   Change inner loop to iterate over all j ≤ i and update dp[i] as max(dp[i], dp[i-j] * dp[j]) without max(j, dp[j]) removes max(j, dp[j]) incorrectly; Keep the same code but add memoization to avoid recomputation adds memoization but doesn't change logic; Sort possible parts and greedily pick the largest part repeatedly to maximize product is greedy and fails on some inputs.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Unbounded knapsack style DP uses dp[i] = max(dp[i], j * dp[i-j]) [OK]

Hint: Unbounded knapsack uses dp[i] = max(dp[i], j * dp[i-j]) [OK]

Common Mistakes:

• Using greedy approach
• Not adjusting DP recurrence for reuse