Bird
Raised Fist0
Interview Prepdp-knapsackmediumAmazonFacebookGoogle

Equal Partition (Partition Equal Subset Sum)

Choose your preparation mode4 modes available
▶
Steps
setup

Calculate total sum and check parity

Calculate the total sum of the array [1,5,11,5], which is 22. Since 22 is even, proceed to find a subset with sum 11.

💡 Checking if the total sum is even is crucial because if it's odd, equal partition is impossible.
Line:total = sum(nums) if total % 2 != 0: return False
💡 The problem reduces to finding a subset with sum equal to half the total sum.
📊
Equal Partition (Partition Equal Subset Sum) - Watch the Algorithm Execute, Step by Step
Watching the dp array update step-by-step reveals how the problem reduces to a subset sum problem and how the algorithm efficiently tracks achievable sums.
Step 1/13
·Active fill★Answer cell
Initializing dp array
i\w01234567891011
i=0????????????
Initializing dp array
i\w01234567891011
i=0TrueFalseFalseFalseFalseFalseFalseFalseFalseFalseFalseFalse
dp[0] = True
Item 0 - wt:1 val:1
i\w01234567891011
i=0TrueFalseFalseFalseFalseFalseFalseFalseFalseFalseFalseFalse
Item 0 - wt:1 val:1
i\w01234567891011
i=0TrueFalseFalseFalseFalseFalseFalseFalseFalseFalseFalseFalse
No update
Item 0 - wt:1 val:1
i\w01234567891011
i=0TrueTrueFalseFalseFalseFalseFalseFalseFalseFalseFalseFalse
dp[1] updated
Item 1 - wt:5 val:5
i\w01234567891011
i=0TrueTrueFalseFalseFalseFalseFalseFalseFalseFalseFalseTrue
dp[11] remains True
Item 1 - wt:5 val:5
i\w01234567891011
i=0TrueTrueFalseFalseFalseFalseTrueFalseFalseFalseFalseTrue
dp[6] updated
Item 1 - wt:5 val:5
i\w01234567891011
i=0TrueTrueFalseFalseFalseTrueTrueFalseFalseFalseFalseTrue
dp[5] updated
Item 2 - wt:11 val:11
i\w01234567891011
i=0TrueTrueFalseFalseFalseTrueTrueFalseFalseFalseFalseTrue
dp[11] updated True
Item 3 - wt:5 val:5
i\w01234567891011
i=0TrueTrueFalseFalseFalseTrueTrueFalseFalseFalseFalseTrue
dp[11] remains True
Item 3 - wt:5 val:5
i\w01234567891011
i=0TrueTrueFalseFalseFalseTrueTrueFalseFalseFalseTrueTrue
dp[10] updated
Item 3 - wt:5 val:5
i\w01234567891011
i=0TrueTrueFalseFalseFalseTrueTrueFalseFalseFalseTrueTrue
dp[5] remains True
Initializing dp array
i\w01234567891011
i=0TrueTrueFalseFalseFalseTrueTrueFalseFalseFalseTrueTrue
Answer: True

Key Takeaways

✓ The problem reduces to checking if a subset sum equal to half the total sum exists.

This insight is hard to see from code alone because the reduction is conceptual, but the visualization shows the target sum clearly.

✓ The dp array tracks achievable sums and updates monotonically as numbers are processed.

Seeing the dp array update step-by-step reveals how sums accumulate and why backward iteration is necessary.

✓ The final answer is simply dp[target], showing if the target sum is achievable after processing all numbers.

This clarifies that the complex problem is solved by a simple boolean check at the end.

Practice

(1/5)
1. Consider the following Python code implementing the optimal job scheduling solution. What is the value of dp[2] after the loop iteration with i=2 when the input is startTime = [1, 2, 3], endTime = [3, 5, 10], and profit = [20, 20, 100]?
easy
A. 120
B. 20
C. 140
D. 100

Solution

  1. Step 1: Sort jobs by end time

    Jobs sorted by end time: [(1,3,20), (2,5,20), (3,10,100)]. Ends = [3,5,10]
  2. Step 2: Calculate dp[2]

    For i=2 (job with start=3, end=10, profit=100): binary search idx = bisect_right(ends, 2) - 1 = 0 (job 0 compatible). take = 100 + dp[0] = 100 + 20 = 120; skip = dp[1] = max profit till job 1 = 20 (from previous iterations). dp[2] = max(120, 20) = 120.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    dp array after iteration 2 is [20, 20, 120] [OK]
Hint: Binary search finds last compatible job index correctly [OK]
Common Mistakes:
  • Off-by-one in binary search index
  • Using dp[i-1] incorrectly
  • Ignoring base case for dp[0]
2. The following code attempts to count the number of combinations to make change. Which line contains a subtle bug that causes it to count permutations instead of combinations?
medium
A. Line 5: inner loop iterating backwards over amounts
B. Line 4: outer loop over coins
C. Line 2: dp initialization
D. Line 6: updating dp[w] with dp[w - coin]

Solution

  1. Step 1: Understand iteration order effect

    Iterating amounts backwards causes dp to count permutations, not combinations.
  2. Step 2: Identify bug line

    Line 5 iterates w from amount down to coin, which breaks combination counting logic.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Forward iteration over amounts is required to count combinations correctly [OK]
Hint: Check direction of inner loop iteration [OK]
Common Mistakes:
  • Using backward iteration in 1D dp
  • Misplacing dp[0] initialization
3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the minimum subset sum difference problem, given an input array of size n and total sum S?
medium
A. O(S^2)
B. O(n^2)
C. O(n * S)
D. O(n * log S)

Solution

  1. Step 1: Identify loops in the code

    Outer loop runs n times (for each element), inner loop runs up to total_sum S times.
  2. Step 2: Calculate total complexity

    Time complexity is O(n * S) because each element updates dp array of size S.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    DP iterates over n elements and sums up to S [OK]
Hint: Time depends on n and total sum, not n squared [OK]
Common Mistakes:
  • Confusing n with S or assuming quadratic n^2
  • Ignoring dp array size impact
4. The following code attempts to solve the subset sum problem using space-optimized DP. Identify the bug that causes incorrect results on some inputs.
medium
A. Line 2: dp[0] should be initialized to False
B. Line 6: dp[w] should be assigned dp[w - num] only, not ORed
C. Line 4: The outer loop should iterate backwards over nums
D. Line 5: The inner loop iterates forwards instead of backwards

Solution

  1. Step 1: Understand dp update direction

    Iterating forwards causes dp[w] to use updated dp[w - num] from the same iteration, leading to overcounting.
  2. Step 2: Correct iteration direction

    Iterating backwards ensures dp[w - num] is from previous iteration, preserving correctness.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Forward iteration breaks subset sum correctness -> bug at line 5 [OK]
Hint: DP must iterate sums backward to avoid reuse in same iteration [OK]
Common Mistakes:
  • Initializing dp[0] incorrectly
  • Misusing OR in dp update
  • Wrong loop order over nums
5. Suppose the coin change problem is modified so that each coin can only be used at most once (0/1 knapsack variant). Which of the following changes to the bottom-up DP approach correctly solves this variant?
hard
A. Use a 2D dp array where dp[i][j] represents minimum coins to make amount j using first i coins, iterating coins outer and amounts inner
B. Sort coins and greedily pick largest coins without repetition until amount is reached
C. Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage)
D. Use the same 1D dp but iterate amounts outer and coins inner, updating dp[j] only if dp[j - coin] was from previous iteration

Solution

  1. Step 1: Understand the 0/1 usage constraint

    Each coin can be used once, so we must track usage per coin, requiring 2D dp.
  2. Step 2: Identify correct DP structure

    2D dp with dp[i][j] = min coins to make j using first i coins ensures no reuse; iterate coins outer, amounts inner.
  3. Step 3: Why other options fail

    Keep the same 1D dp array and iterate coins inside the amount loop as before (unbounded usage) allows unlimited reuse; B is greedy and incorrect; D misuses 1D dp which is for unbounded usage.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    0/1 knapsack requires 2D dp to track coin usage [OK]
Hint: 0/1 knapsack needs 2D dp to prevent reuse [OK]
Common Mistakes:
  • Using unbounded knapsack DP for 0/1 problem
  • Assuming greedy works for minimum coins
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