💡 This formula computes the difference between two subsets with sums 11 and 12.
Line:return total_sum - 2 * w
💡 The minimal difference between subset sums is 1.
result
Final result: minimal subset sum difference is 1
Return the minimal difference 1 as the final answer, concluding the algorithm.
💡 The minimal difference of 1 means the array can be partitioned into two subsets with sums differing by only 1.
Line:return total_sum - 2 * w
💡 This final step confirms the correctness and completeness of the DP approach.
def min_subset_sum_diff(arr):
total_sum = sum(arr) # STEP 1
dp = [False] * (total_sum + 1) # STEP 1
dp[0] = True # STEP 1
for item_index, num in enumerate(arr): # STEP 2-5
for w in range(total_sum, num - 1, -1): # STEP 2-5
dp[w] = dp[w] or dp[w - num] # STEP 2-5
half = total_sum // 2 # STEP 6
for w in range(half, -1, -1): # STEP 7
if dp[w]: # STEP 7
return total_sum - 2 * w # STEP 8
if __name__ == '__main__':
arr = [1, 6, 11, 5]
print(min_subset_sum_diff(arr)) # Output: 1
📊
Minimum Subset Sum Difference - Watch the Algorithm Execute, Step by Step
Watching the step-by-step updates of the DP array reveals how subset sums accumulate and why checking sums up to half the total sum is sufficient to find the minimal difference.
Step 1/10
·Active fill★Answer cell
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i=0
True
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
dp[0] = True (base)
Item 0 - wt:1 val:1
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i=0
True
True
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
dp[0] True base
Item 1 - wt:6 val:6
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i=0
True
True
False
False
False
False
True
True
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
False
dp[0] True base
Item 2 - wt:11 val:11
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i=0
True
True
False
False
False
False
True
True
False
False
False
True
True
False
False
False
False
True
True
False
False
False
False
False
dp[0] True base
Item 3 - wt:5 val:5
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i=0
True
True
False
False
False
True
True
True
False
False
False
True
True
False
False
False
True
True
True
False
False
False
True
True
dp[0] True base
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i=0
True
True
False
False
False
True
True
True
False
False
False
True
True
False
False
False
True
True
True
False
False
False
True
True
half = 11
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i=0
True
True
False
False
False
True
True
True
False
False
False
True
True
False
False
False
True
True
True
False
False
False
True
True
Checking dp[11]
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i=0
True
True
False
False
False
True
True
True
False
False
False
True
True
False
False
False
True
True
True
False
False
False
True
True
dp[11] True - chosen sum
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i=0
True
True
False
False
False
True
True
True
False
False
False
True
True
False
False
False
True
True
True
False
False
False
True
True
Answer cell
Initializing dp array
i\w
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i=0
True
True
False
False
False
True
True
True
False
False
False
True
True
False
False
False
True
True
True
False
False
False
True
True
Answer cell
Key Takeaways
✓ The DP array tracks which subset sums are achievable as elements are processed.
This insight is hard to see from code alone because the boolean array updates are subtle and cumulative.
✓ Backward iteration over sums prevents reuse of the same element multiple times in one iteration.
Visualizing the backward update clarifies why this order is necessary for correctness.
✓ The minimal difference is found by scanning achievable sums only up to half the total sum.
This reduces the search space and is a key optimization that is not obvious without seeing the DP array.
Practice
(1/5)
1. Consider the following Python code for counting the number of ways to make change. What is the output when calling change(5, [1, 2, 5])?
easy
A. 5
B. 3
C. 4
D. 6
Solution
Step 1: Initialize dp array
dp = [1,0,0,0,0,0] since dp[0]=1.
Step 2: Update dp for each coin
For coin=1: dp becomes [1,1,1,1,1,1]; for coin=2: dp updates to [1,1,2,2,3,3]; for coin=5: dp updates to [1,1,2,2,3,4].
Final Answer:
Option C -> Option C
Quick Check:
dp[5] = 4 matches known output [OK]
Hint: Trace dp updates coin by coin [OK]
Common Mistakes:
Off-by-one in dp indexing
Confusing permutations with combinations
2. Consider the following Python code for the Equal Partition problem. What is the value of dp[target] after processing the input [1, 5, 11, 5]?
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for w in range(target, num - 1, -1):
dp[w] = dp[w] or dp[w - num]
return dp[target]
print(canPartition([1,5,11,5]))
easy
A. true
B. false
C. null (error occurs)
D. Depends on order of iteration
Solution
Step 1: Calculate total and target
The total sum is 1 + 5 + 11 + 5 = 22, which is even, so target = 11.
Step 2: Trace dp array updates for each num
After processing all nums, dp[11] becomes True because subset {11} or {5,5,1} sums to 11.
Final Answer:
Option A -> Option A
Quick Check:
Input is classic example where partition exists; dp[target] is True [OK]
Hint: Sum is even and dp[target] tracks subset sums [OK]
Common Mistakes:
Confusing dp[target] with dp[target-1]
Forgetting to iterate backwards in dp update
3. You need to find the number of distinct ways to make a target amount using unlimited supply of given coin denominations. Which algorithmic approach guarantees counting all unique combinations without overcounting permutations?
easy
A. Greedy algorithm that picks the largest coin first until the amount is reached
B. Dynamic programming using a 1D array iterating coins first, then amounts
C. Backtracking exploring all permutations of coins to sum to the amount
D. Sorting coins and using two pointers to find pairs that sum to the amount
Solution
Step 1: Understand problem constraints
The problem requires counting unique combinations, not permutations, of coins to reach the target amount.
Step 2: Identify algorithm that counts combinations without duplicates
Dynamic programming iterating coins first ensures each coin is considered in order, avoiding counting permutations multiple times. The 1D DP approach efficiently accumulates counts for each amount.
Final Answer:
Option B -> Option B
Quick Check:
DP with coin-first iteration counts combinations correctly [OK]
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
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.
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.
Final Answer:
Option C -> Option C
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 problem is modified so that each string can be chosen multiple times (unbounded usage). Which change to the dynamic programming approach correctly adapts the solution?
hard
A. Iterate dp array forwards to allow multiple counts of the same string
B. Iterate dp array backwards as before to avoid counting duplicates
C. Use recursion without memoization to handle repeated choices
D. Increase dp dimensions to track usage count of each string
Solution
Step 1: Understand difference between 0/1 and unbounded knapsack
Unbounded knapsack allows multiple uses of the same item, so dp updates must allow reuse within the same iteration.
Step 2: Adjust dp iteration order
Iterating dp forwards enables using updated states multiple times, correctly counting repeated strings.
Step 3: Confirm correctness
Backward iteration prevents reuse in the same iteration, which is incorrect for unbounded usage.