💡 This initialization sets the base case for the dynamic programming approach.
fill_cells
Start processing first number: 1
Begin processing the first number 1. We will update dp array for sums from target down to 1.
💡 Processing each number updates achievable sums in dp array.
Line:for w in range(target, num - 1, -1):
dp[w] = dp[w] or dp[w - num]
💡 We check if sum w can be formed either previously or by adding current number 1 to a previously achievable sum w-1.
fill_cells
Update dp for w=11 with number 1
Check if sum 11 can be achieved by including number 1: dp[11] = dp[11] or dp[10]. Both are False, so dp[11] remains False.
💡 At w=11, no new sum achievable by adding 1.
Line:dp[11] = dp[11] or dp[11 - 1]
💡 No change at dp[11] since dp[10] is False.
fill_cells
Update dp for w=1 with number 1
Check if sum 1 can be achieved by including number 1: dp[1] = dp[1] or dp[0]. dp[0] is True, so dp[1] becomes True.
💡 Sum 1 is now achievable by including number 1.
Line:dp[1] = dp[1] or dp[1 - 1]
💡 dp[1] updated to True, reflecting achievable sum.
fill_cells
Process second number: 5, start with w=11
Process number 5. For w=11, update dp[11] = dp[11] or dp[6]. dp[6] is False, so dp[11] remains True from previous step.
💡 Check if sum 11 achievable by adding 5 to sum 6.
Line:dp[11] = dp[11] or dp[11 - 5]
💡 No change at dp[11] since dp[6] is False.
fill_cells
Update dp for w=6 with number 5
Check if sum 6 can be achieved by including number 5: dp[6] = dp[6] or dp[1]. dp[1] is True, so dp[6] becomes True.
💡 Sum 6 is now achievable by adding 5 to sum 1.
Line:dp[6] = dp[6] or dp[6 - 5]
💡 dp[6] updated to True.
fill_cells
Update dp for w=5 with number 5
Check if sum 5 can be achieved by including number 5: dp[5] = dp[5] or dp[0]. dp[0] is True, so dp[5] becomes True.
💡 Sum 5 is now achievable by including number 5 alone.
Line:dp[5] = dp[5] or dp[5 - 5]
💡 dp[5] updated to True.
fill_cells
Process third number: 11 (w=11 only)
Process number 11. Only w=11 is valid for update: dp[11] = dp[11] or dp[0]. Since dp[0] is True, dp[11] remains True.
💡 Including 11 allows achieving sum 11 directly.
Line:for w in range(target, num - 1, -1):
dp[w] = dp[w] or dp[w - num]
💡 This step shows how a large number can directly achieve the target sum.
fill_cells
Process fourth number: 5, start with w=11
Process last number 5. For w=11, update dp[11] = dp[11] or dp[6]. dp[6] is True, so dp[11] remains True.
💡 Check if sum 11 achievable by adding 5 to sum 6.
Line:dp[11] = dp[11] or dp[11 - 5]
💡 dp[11] remains True.
fill_cells
Update dp for w=10 with number 5
Check if sum 10 can be achieved by including number 5: dp[10] = dp[10] or dp[5]. dp[5] is True, so dp[10] becomes True.
💡 Sum 10 is now achievable by adding 5 to sum 5.
Line:dp[10] = dp[10] or dp[10 - 5]
💡 dp[10] updated to True.
fill_cells
Update dp for w=5 with number 5
Check if sum 5 can be achieved by including number 5: dp[5] = dp[5] or dp[0]. dp[0] is True, so dp[5] remains True.
💡 Sum 5 remains achievable.
Line:dp[5] = dp[5] or dp[5 - 5]
💡 No change at dp[5].
traverse
Check final answer at dp[target]
Check dp[11], which is True, indicating a subset with sum 11 exists, so the array can be partitioned equally.
💡 The final dp cell tells if the target sum is achievable.
Line:return dp[target]
💡 The problem reduces to checking dp[target] after processing all numbers.
def canPartition(nums):
total = sum(nums) # STEP 1
if total % 2 != 0: # STEP 1
return False
target = total // 2 # STEP 2
dp = [False] * (target + 1) # STEP 2
dp[0] = True # STEP 2
for i, num in enumerate(nums): # STEP 3-12
for w in range(target, num - 1, -1):
dp[w] = dp[w] or dp[w - num]
return dp[target] # STEP 13
if __name__ == '__main__':
print(canPartition([1,5,11,5])) # True
print(canPartition([1,2,3,5])) # False
📊
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\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
?
?
?
?
?
?
?
?
?
?
?
?
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
False
False
False
False
False
False
False
False
False
False
False
dp[0] = True
Item 0 - wt:1 val:1
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
False
False
False
False
False
False
False
False
False
False
False
Item 0 - wt:1 val:1
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
False
False
False
False
False
False
False
False
False
False
False
No update
Item 0 - wt:1 val:1
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
False
False
False
False
False
False
False
False
False
False
dp[1] updated
Item 1 - wt:5 val:5
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
False
False
False
False
False
False
False
False
False
True
dp[11] remains True
Item 1 - wt:5 val:5
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
False
False
False
False
True
False
False
False
False
True
dp[6] updated
Item 1 - wt:5 val:5
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
False
False
False
True
True
False
False
False
False
True
dp[5] updated
Item 2 - wt:11 val:11
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
False
False
False
True
True
False
False
False
False
True
dp[11] updated True
Item 3 - wt:5 val:5
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
False
False
False
True
True
False
False
False
False
True
dp[11] remains True
Item 3 - wt:5 val:5
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
False
False
False
True
True
False
False
False
True
True
dp[10] updated
Item 3 - wt:5 val:5
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
False
False
False
True
True
False
False
False
True
True
dp[5] remains True
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
11
i=0
True
True
False
False
False
True
True
False
False
False
True
True
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
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]
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
Step 1: Understand iteration order effect
Iterating amounts backwards causes dp to count permutations, not combinations.
Step 2: Identify bug line
Line 5 iterates w from amount down to coin, which breaks combination counting logic.
Final Answer:
Option A -> Option A
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
Step 1: Identify loops in the code
Outer loop runs n times (for each element), inner loop runs up to total_sum S times.
Step 2: Calculate total complexity
Time complexity is O(n * S) because each element updates dp array of size S.
Final Answer:
Option C -> Option C
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
Step 1: Understand dp update direction
Iterating forwards causes dp[w] to use updated dp[w - num] from the same iteration, leading to overcounting.
Step 2: Correct iteration direction
Iterating backwards ensures dp[w - num] is from previous iteration, preserving correctness.
Final Answer:
Option D -> Option D
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
Step 1: Understand the 0/1 usage constraint
Each coin can be used once, so we must track usage per coin, requiring 2D dp.
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.
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.
Final Answer:
Option A -> Option A
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 unknownstrongwhile earning +1 Grip toward your certificate.