💡 Cannot add element 1 to subset {0} as sum would exceed target.
fill_cells
Continue expanding subsets until full mask reachable
Iterate through all masks and elements, updating dp for reachable subsets by adding elements without exceeding target.
💡 This systematic expansion explores all subset combinations efficiently.
Line:for mask in range(1 << n):
if dp[mask] == -1:
continue
for i in range(n):
if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
next_mask = mask | (1 << i)
if dp[next_mask] == -1:
dp[next_mask] = (dp[mask] + nums[i]) % target
💡 The DP table eventually marks the full set mask reachable with sum 0 mod target, meaning partitioning is possible.
compare
Check final dp value for full mask
Check dp value for mask with all elements included to determine if partitioning is possible.
💡 If dp for full mask is 0, it means all elements can be partitioned into k subsets with equal sum.
Line:return dp[(1 << n) - 1] == 0
💡 The full set is reachable with sum modulo target 0, confirming valid partitioning.
from typing import List
def canPartitionKSubsets(nums: List[int], k: int) -> bool:
total = sum(nums) # STEP 1
if total % k != 0: # STEP 1
return False
target = total // k # STEP 1
n = len(nums)
nums.sort() # STEP 2
if nums[-1] > target: # STEP 2
return False
dp = [-1] * (1 << n) # STEP 3
dp[0] = 0 # STEP 3
for mask in range(1 << n): # STEP 4, 14
if dp[mask] == -1:
continue
for i in range(n): # STEP 5-13
if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
next_mask = mask | (1 << i)
if dp[next_mask] == -1:
dp[next_mask] = (dp[mask] + nums[i]) % target
return dp[(1 << n) - 1] == 0 # STEP 15
📊
Partition to K Equal Sum Subsets - Watch the Algorithm Execute, Step by Step
Watching this visualization helps you understand how bitmask DP explores all subsets efficiently and how the modulo operation tracks partial sums for equal partitions.
Step 1/15
·Active fill★Answer cell
Initializing dp array
i\w
Initializing dp array
i\w
Initializing dp array
i\w
0
i=0
0
dp[0] = 0 (empty subset)
Initializing dp array
i\w
0
i=0
0
Current mask = 0 (empty subset)
Item 6 - 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
i=0
0
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
mask=0 (empty subset)
Item 2 - wt:2 val:2
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
i=0
0
?
?
?
2
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
mask=0 (empty subset)
Item 1 - wt:2 val:2
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
i=0
0
?
2
?
2
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
mask=0 (empty subset)
Item 4 - wt:4 val:4
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
i=0
0
?
2
?
2
?
?
?
?
?
?
?
?
?
?
?
4
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
mask=0 (empty subset)
Item 3 - wt:3 val:3
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
i=0
0
?
2
?
2
?
?
?
3
?
?
?
?
?
?
?
4
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
mask=0 (empty subset)
Item 5 - wt:3 val:3
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
i=0
0
?
2
?
2
?
?
?
3
?
?
?
?
?
?
?
4
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3
?
?
?
?
?
?
?
?
?
?
?
mask=0 (empty subset)
Item 0 - wt:4 val:4
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
i=0
0
4
2
?
2
?
?
?
3
?
?
?
?
?
?
?
4
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3
?
?
?
?
?
?
?
?
?
?
?
mask=0 (empty subset)
Item 6 - 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
i=0
0
4
2
?
2
?
?
?
3
?
?
?
?
?
?
?
4
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3
?
?
?
?
?
?
?
?
?
?
0
mask=1 (subset {0})
Item 1 - wt:2 val:2
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
i=0
0
4
2
?
2
?
?
?
3
?
?
?
?
?
?
?
4
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
3
?
?
?
?
?
?
?
?
?
?
0
mask=1 (subset {0})
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
i=0
0
4
2
3
2
3
4
0
3
4
0
1
1
2
3
4
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
DP table partially filled
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
i=0
0
4
2
3
2
3
4
0
3
4
0
1
1
2
3
4
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
0
1
2
0
Answer cell dp[127] = 0 (partition possible)
Key Takeaways
✓ Bitmask DP efficiently explores all subsets by representing them as integers and tracking partial sums modulo target.
This insight is hard to see from code alone because the bitmask representation and modulo arithmetic are abstract concepts.
✓ The DP table's fill order depends on reachable subsets, ensuring no redundant computations and pruning unreachable states.
Visualizing the fill order clarifies why some subsets are never reached and how the algorithm avoids unnecessary work.
✓ The final decision depends on whether the full set mask is reachable with sum modulo target zero, confirming equal partitioning.
Seeing the final dp cell highlighted as the answer cell concretely connects the DP state to the problem's solution.
Practice
(1/5)
1. Given the following code for lastStoneWeightII, what is the returned value when stones = [1, 2, 3]?
For weight=1: dp[1]=true; for weight=2: dp[3]=true (since dp[1] was true), dp[2]=true; for weight=3: dp[3]=true remains.
Step 3: Find largest w ≤ half with dp[w] = true
dp[3] is true, so minimal difference = total - 2*3 = 6 - 6 = 0.
Final Answer:
Option B -> Option B
Quick Check:
Subset {1,2,3} sums to 6; partition into {3} and {1,2} sums 3 and 3 -> difference 0 [OK]
Hint: Check dp array for sums up to half total [OK]
Common Mistakes:
Returning total instead of minimal difference
Off-by-one error in dp indexing
Not iterating backwards in dp update
2. Consider the following Python function implementing the Target Sum problem using bottom-up DP with offset indexing. What is the returned value when calling findTargetSumWays([1, 2], 1)?
easy
A. 1
B. 3
C. 0
D. 2
Solution
Step 1: Trace initial dp array
total=3, offset=3, dp=[0,0,0,1,0,0,0] (index 3 corresponds to sum 0)
Step 2: Process num=1 and num=2 updating dp
After num=1, dp counts ways to reach sums -1 and 1. After num=2, dp counts ways to reach sums -3,-1,1,3. dp[target+offset]=dp[1+3]=dp[4]=2.
Final Answer:
Option D -> Option D
Quick Check:
Two ways: +1-2 and -1+2 sum to 1 [OK]
Hint: Offset indexing maps sums to dp indices [OK]
Common Mistakes:
Off-by-one errors in indexing dp array
3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the Equal Partition problem, where n is the number of elements and target is half the total sum?
medium
A. O(2^n) because the problem explores all subsets in worst case
B. O(n * n) because we iterate over all elements and all sums up to n
C. O(target^2) because the dp array size is target and we update it multiple times
D. O(n * target) because for each element we iterate over sums up to target
Solution
Step 1: Identify loops in the code
The outer loop runs n times (for each element), and the inner loop runs up to target times (half the total sum).
Step 2: Calculate total time complexity
Multiplying these gives O(n * target). The dp array updates are constant time per iteration.
Final Answer:
Option D -> Option D
Quick Check:
Time depends on number of elements and target sum, not n squared or exponential [OK]
Hint: Time depends on n and target sum, not just n [OK]
Common Mistakes:
Confusing n with target or assuming quadratic in n
Forgetting target can be large
4. Examine the following buggy code snippet for the minimum cost tickets problem. Which line contains the subtle bug that can cause incorrect results on some inputs?
medium
A. Line with dp initialization: dp = [0] * (n + 1)
B. Line updating dp[i] = ans after inner loop
C. Line setting ans = float('inf') inside outer loop
D. Line with bisect.bisect_left call searching from 0 instead of i
Solution
Step 1: Identify bisect usage
Binary search must start from current index i to avoid counting days before i. Searching from 0 can cause next_i to point to an earlier day, leading to incorrect dp indexing.
Step 2: Confirm other lines are correct
dp initialization, ans reset, and dp assignment are standard and correct. The bug is only in bisect call range.
Final Answer:
Option D -> Option D
Quick Check:
Correct bisect range is [i, n), not [0, n) [OK]
Hint: Check bisect search range carefully [OK]
Common Mistakes:
Using full array in bisect causing wrong next_i
Forgetting to reset ans
Incorrect dp array size
5. Suppose the problem is modified so that each coin can be used at most once (0/1 knapsack variant). Which of the following changes to the original code correctly counts the number of combinations?
hard
A. Change inner loop to iterate amounts backward (from amount down to coin) to avoid reuse
B. Change inner loop to iterate amounts forward (from coin to amount) as in original code
C. Use recursion without memoization to explore all subsets
D. Use greedy approach picking largest coins first
Solution
Step 1: Understand 0/1 knapsack constraints
Each coin can be used once, so dp updates must avoid reuse within same iteration.