Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonFacebookGoogle

Equal Partition (Partition Equal Subset Sum)

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"nums":[1,5,11,5]}
Expectedtrue

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

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

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

t2_01edge
Input{"nums":[]}
Expectedtrue

Empty array cannot be partitioned into two equal subsets.

t2_02edge
Input{"nums":[1]}
Expectedfalse

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

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

All elements identical and even count can be partitioned equally.

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

Large element with small others cannot be partitioned equally.

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

Sum is odd (5), so partition impossible.

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

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

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]}
⏱ 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.

Practice

(1/5)
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 integer break. What is the value of dp[3] after the outer loop iteration i = 3 completes?
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]

print(integer_break(4))  # Output not asked here
easy
A. 2
B. 4
C. 3
D. 1

Solution

  1. Step 1: Trace dp for i=2

    dp[1] = 1 (given). For i=2, j=1: max_product = max(0, max(1,1)*max(1,1)) = 1, so dp[2] = 1.
  2. Step 2: Trace dp for i=3

    j=1: max_product = max(0, max(1,1)*max(2,dp[2])) = max(0,1*2) = 2 j=2: max_product = max(2, max(2,dp[2])*max(1,dp[1])) = max(2,2*1) = 2 So dp[3] = 2.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    dp[3] = 2 matches manual calculation [OK]
Hint: Trace inner loop carefully for each j [OK]
Common Mistakes:
  • Off-by-one in loop bounds
  • Confusing dp[i-j] with dp[j]
3. 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
4. What is the time complexity of the optimal bottom-up dynamic programming solution for the Coin Change II problem with n coins and target amount amount?
medium
A. O(amount^2)
B. O(n + amount)
C. O(2^amount)
D. O(n * amount)

Solution

  1. Step 1: Identify loops in code

    Outer loop iterates over n coins, inner loop iterates over amount from coin to amount.
  2. Step 2: Calculate complexity

    Each dp[w] update is O(1), total updates are roughly n * amount, so time complexity is O(n * amount).
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Nested loops over coins and amounts confirm O(n * amount) [OK]
Hint: Count nested loops and their ranges [OK]
Common Mistakes:
  • Confusing amount with n
  • Forgetting recursion stack space
  • Assuming quadratic in amount
5. 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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard