Subset Sum

▶

Steps

setup

Initialize dp array

Create a dp array of size S+1 (10) initialized to False, then set dp[0] to True because sum 0 is always achievable with no elements.

💡 This initialization sets the base case: sum zero is always possible by choosing no elements.

Line:

dp = [False] * (S + 1)
dp[0] = True

💡 The dp array tracks which sums are achievable; starting with only sum 0 achievable.

fill_cells

Process first number: 3

Start processing the first number 3. We will update dp[w] for w from 9 down to 3.

💡 Processing each number updates achievable sums by considering if adding this number helps reach new sums.

Line:

for w in range(S, num - 1, -1):

💡 We iterate backwards to avoid using the same number multiple times in one iteration.

compare

Check dp[9] with num=3

Check if sum 9 can be formed by adding 3 to a previously achievable sum dp[6]. dp[6] is False, so dp[9] remains False.

💡 We check if dp[9] can be True by dp[9] or dp[6], but dp[6] is False so no update.

Line:

dp[9] = dp[9] or dp[9 - 3]

💡 Sum 9 is not achievable yet using 3 and previous sums.

compare

Check dp[8] with num=3

Check if sum 8 can be formed by adding 3 to dp[5]. dp[5] is False, so dp[8] remains False.

💡 We test if dp[8] can be True by dp[8] or dp[5], but dp[5] is False so no update.

Line:

dp[8] = dp[8] or dp[8 - 3]

💡 Sum 8 is not achievable yet using 3 and previous sums.

compare

Check dp[7] with num=3

Check if sum 7 can be formed by adding 3 to dp[4]. dp[4] is False, so dp[7] remains False.

💡 We test if dp[7] can be True by dp[7] or dp[4], but dp[4] is False so no update.

Line:

dp[7] = dp[7] or dp[7 - 3]

💡 Sum 7 is not achievable yet using 3 and previous sums.

compare

Check dp[6] with num=3

Check if sum 6 can be formed by adding 3 to dp[3]. dp[3] is False, so dp[6] remains False.

💡 We test if dp[6] can be True by dp[6] or dp[3], but dp[3] is False so no update.

Line:

dp[6] = dp[6] or dp[6 - 3]

💡 Sum 6 is not achievable yet using 3 and previous sums.

compare

Check dp[5] with num=3

Check if sum 5 can be formed by adding 3 to dp[2]. dp[2] is False, so dp[5] remains False.

💡 We test if dp[5] can be True by dp[5] or dp[2], but dp[2] is False so no update.

Line:

dp[5] = dp[5] or dp[5 - 3]

💡 Sum 5 is not achievable yet using 3 and previous sums.

compare

Check dp[4] with num=3

Check if sum 4 can be formed by adding 3 to dp[1]. dp[1] is False, so dp[4] remains False.

💡 We test if dp[4] can be True by dp[4] or dp[1], but dp[1] is False so no update.

Line:

dp[4] = dp[4] or dp[4 - 3]

💡 Sum 4 is not achievable yet using 3 and previous sums.

compare

Check dp[3] with num=3

Check if sum 3 can be formed by adding 3 to dp[0]. dp[0] is True, so dp[3] becomes True.

💡 Since dp[0] is True, adding 3 means sum 3 is now achievable.

Line:

dp[3] = dp[3] or dp[3 - 3]

💡 We found a new achievable sum: 3.

fill_cells

Process second number: 34 (skipped)

Next number is 34, which is greater than S=9, so no dp updates occur.

💡 Numbers larger than the target sum cannot contribute to forming sums ≤ S.

Line:

for w in range(S, num - 1, -1):  # no iterations since 34 > 9

💡 Large numbers are ignored as they cannot help form sums ≤ S.

fill_cells

Process third number: 4

Process number 4, update dp[w] for w from 9 down to 4.

💡 Adding 4 may enable new sums by combining with previously achievable sums.

Line:

for w in range(S, num - 1, -1):

💡 We try to form sums including 4.

compare

Check dp[9] with num=4

Check if sum 9 can be formed by adding 4 to dp[5]. dp[5] is False, so dp[9] remains False.

💡 dp[9] depends on dp[5], which is False, so no update.

Line:

dp[9] = dp[9] or dp[9 - 4]

💡 Sum 9 not achievable yet with 4.

compare

Check dp[7] with num=4

Check if sum 7 can be formed by adding 4 to dp[3]. dp[3] is True, so dp[7] becomes True.

💡 Since dp[3] is True, adding 4 means sum 7 is now achievable.

Line:

dp[7] = dp[7] or dp[7 - 4]

💡 New achievable sum 7 found by combining 3 and 4.

compare

Check dp[4] with num=4

Check if sum 4 can be formed by adding 4 to dp[0]. dp[0] is True, so dp[4] becomes True.

💡 Sum 4 is achievable directly by the number 4 itself.

Line:

dp[4] = dp[4] or dp[4 - 4]

💡 We found sum 4 achievable by using the number 4 alone.

fill_cells

Process fourth number: 12 (skipped)

Number 12 is greater than S=9, so no dp updates occur.

💡 Skip numbers larger than target sum as they cannot help form sums ≤ S.

Line:

for w in range(S, num - 1, -1):  # no iterations since 12 > 9

💡 Large numbers are ignored.

fill_cells

Process fifth number: 5

Process number 5, update dp[w] for w from 9 down to 5.

💡 Adding 5 may enable new sums by combining with previously achievable sums.

Line:

for w in range(S, num - 1, -1):

💡 Try to form sums including 5.

compare

Check dp[9] with num=5

Check if sum 9 can be formed by adding 5 to dp[4]. dp[4] is True, so dp[9] becomes True.

💡 Since dp[4] is True, adding 5 means sum 9 is now achievable.

Line:

dp[9] = dp[9] or dp[9 - 5]

💡 We found the target sum 9 achievable by combining 4 and 5.

compare

Check dp[8] with num=5

Check if sum 8 can be formed by adding 5 to dp[3]. dp[3] is True, so dp[8] becomes True.

💡 Since dp[3] is True, adding 5 means sum 8 is now achievable.

Line:

dp[8] = dp[8] or dp[8 - 5]

💡 New achievable sum 8 found by combining 3 and 5.

fill_cells

Process sixth number: 2

Process number 2, update dp[w] for w from 9 down to 2.

💡 Adding 2 may enable new sums by combining with previously achievable sums.

Line:

for w in range(S, num - 1, -1):

💡 Try to form sums including 2.

compare

Check dp[6] with num=2

Check if sum 6 can be formed by adding 2 to dp[4]. dp[4] is True, so dp[6] becomes True.

💡 Since dp[4] is True, adding 2 means sum 6 is now achievable.

Line:

dp[6] = dp[6] or dp[6 - 2]

💡 New achievable sum 6 found by combining 4 and 2.

def subset_sum(nums, S):
    dp = [False] * (S + 1)  # STEP 1: Initialize dp array
    dp[0] = True  # STEP 1
    for i, num in enumerate(nums):  # STEP 2, 10, 15, 16, 19
        for w in range(S, num - 1, -1):  # STEP 2-9, 12-14, 17-18, 20
            dp[w] = dp[w] or dp[w - num]  # STEP 3-9, 12-14, 17-18, 20
    return dp[S]  # STEP 21: Return final answer

if __name__ == '__main__':
    nums = [3, 34, 4, 12, 5, 2]
    S = 9
    print(subset_sum(nums, S))  # True

📊

Subset Sum - Watch the Algorithm Execute, Step by Step

Watching the dp array update step-by-step reveals how the algorithm builds solutions from smaller subproblems, making the logic crystal clear.

Initializing dp array

i\w	0	1	2	3	4	5	6	7	8	9
i=0

dp[0] = True (base case)

Item 0 - wt:3 val:3

i\w	0	1	2	3	4	5	6	7	8	9
i=0

dp array before processing 3

Item 0 - wt:3 val:3

i\w	0	1	2	3	4	5	6	7	8	9
i=0

Check dp[9] = dp[9] or dp[6]

Item 0 - wt:3 val:3

i\w	0	1	2	3	4	5	6	7	8	9
i=0

Check dp[8] = dp[8] or dp[5]

Item 0 - wt:3 val:3

i\w	0	1	2	3	4	5	6	7	8	9
i=0

Check dp[7] = dp[7] or dp[4]

Item 0 - wt:3 val:3

i\w	0	1	2	3	4	5	6	7	8	9
i=0

Check dp[6] = dp[6] or dp[3]

Item 0 - wt:3 val:3

i\w	0	1	2	3	4	5	6	7	8	9
i=0

Check dp[5] = dp[5] or dp[2]

Item 0 - wt:3 val:3

i\w	0	1	2	3	4	5	6	7	8	9
i=0

Check dp[4] = dp[4] or dp[1]

Item 0 - wt:3 val:3

i\w	0	1	2	3	4	5	6	7	8	9
i=0

dp[3] updated to True

Item 1 - wt:34 val:34

i\w	0	1	2	3	4	5	6	7	8	9
i=0

No update for 34

Item 2 - wt:4 val:4

i\w	0	1	2	3	4	5	6	7	8	9
i=0

dp before processing 4

Item 2 - wt:4 val:4

i\w	0	1	2	3	4	5	6	7	8	9
i=0

Check dp[9] = dp[9] or dp[5]

Item 2 - wt:4 val:4

i\w	0	1	2	3	4	5	6	7	8	9
i=0

dp[7] updated to True

Item 2 - wt:4 val:4

i\w	0	1	2	3	4	5	6	7	8	9
i=0

dp[4] updated to True

Item 3 - wt:12 val:12

i\w	0	1	2	3	4	5	6	7	8	9
i=0

No update for 12

Item 4 - wt:5 val:5

i\w	0	1	2	3	4	5	6	7	8	9
i=0

dp before processing 5

Item 4 - wt:5 val:5

i\w	0	1	2	3	4	5	6	7	8	9
i=0

dp[9] updated to True

Item 4 - wt:5 val:5

i\w	0	1	2	3	4	5	6	7	8	9
i=0

dp[8] updated to True

Item 5 - wt:2 val:2

i\w	0	1	2	3	4	5	6	7	8	9
i=0

dp before processing 2

Item 5 - wt:2 val:2

i\w	0	1	2	3	4	5	6	7	8	9
i=0

dp[6] updated to True

Key Takeaways

✓ The dp array tracks which sums are achievable and updates only from smaller sums to larger sums.

This insight is hard to see from code alone because the backward iteration and boolean logic are subtle.

✓ Numbers larger than the target sum are skipped, showing the algorithm's efficiency in ignoring irrelevant elements.

Seeing this visually clarifies why large numbers don't affect the dp array.

✓ When dp[w] changes from False to True, it means a new sum is achievable by including the current number.

Watching these transitions step-by-step reveals how the solution builds incrementally.

Practice

1. You are given a list of binary strings and two integers representing the maximum number of zeros and ones you can use. You want to find the largest subset of these strings such that the total zeros and ones in the subset do not exceed the given limits. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. A greedy algorithm that picks strings with the smallest length first

B. A graph traversal algorithm that finds the shortest path covering all strings

C. A simple recursion that tries all subsets without memoization

D. A dynamic programming approach that uses a 2D state representing zeros and ones capacity

Solution

1. Step 1: Understand problem constraints

   The problem requires selecting a subset of strings constrained by two resources: zeros and ones counts.

2. Step 2: Identify suitable algorithm

   Dynamic programming with a 2D state (zeros and ones) efficiently explores all feasible subsets and ensures optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP with 2D state matches problem constraints [OK]

Hint: Two resource constraints -> 2D DP knapsack [OK]

Common Mistakes:

• Assuming greedy works for multi-constraint knapsack
• Ignoring one resource dimension in DP

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 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

1. 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).

2. Step 2: Calculate total time complexity

   Multiplying these gives O(n * target). The dp array updates are constant time per iteration.

3. Final Answer:

   Option D -> Option D

4. 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. The following code attempts to solve the Partition to K Equal Sum Subsets problem using DP with bitmask tabulation. Identify the line containing the subtle bug that can cause incorrect results or infinite loops.

def canPartitionKSubsets(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort()
    if nums[-1] > target:
        return False

    dp = [-1] * (1 << n)
    dp[0] = 0

    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)
                dp[next_mask] = (dp[mask] + nums[i]) % target

    return dp[(1 << n) - 1] == 0

medium

A. Line: dp = [-1] * (1 << n)

B. Line: if dp[next_mask] == -1: (missing in this code)

C. Line: nums.sort()

D. Line: dp[next_mask] = (dp[mask] + nums[i]) % target

Solution

1. Step 1: Identify missing condition

   The code lacks a check if dp[next_mask] is already set, so it overwrites states, causing incorrect results.

2. Step 2: Pinpoint the buggy line

   The line assigning dp[next_mask] unconditionally overwrites previous valid states, breaking memoization.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding "if dp[next_mask] == -1:" before assignment fixes bug [OK]

Hint: Always check if dp state is unset before assignment [OK]

Common Mistakes:

• Overwriting dp states without checking leads to incorrect answers
• Not pruning symmetric states increases runtime

5. Suppose the integer break problem is modified so that you can reuse the same integer parts multiple times (unbounded splits), and you want to find the maximum product. Which modification to the DP approach below correctly handles this variant?

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]

Options:

hard

A. Use a nested loop where for each i, iterate j from 1 to i and update dp[i] = max(dp[i], j * dp[i-j]) to allow reuse

B. Sort possible parts and greedily pick the largest part repeatedly to maximize product

C. Keep the same code but add memoization to avoid recomputation

D. Change inner loop to iterate over all j ≤ i and update dp[i] as max(dp[i], dp[i-j] * dp[j]) without max(j, dp[j])

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means dp[i] depends on dp[i-j] multiplied by j (or dp[j]) where j can be reused multiple times.

2. Step 2: Modify DP update

   Updating dp[i] = max(dp[i], j * dp[i-j]) correctly models unbounded splits by combining current part j and best product for remaining i-j.

3. Step 3: Evaluate other options

   Change inner loop to iterate over all j ≤ i and update dp[i] as max(dp[i], dp[i-j] * dp[j]) without max(j, dp[j]) removes max(j, dp[j]) incorrectly; Keep the same code but add memoization to avoid recomputation adds memoization but doesn't change logic; Sort possible parts and greedily pick the largest part repeatedly to maximize product is greedy and fails on some inputs.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Unbounded knapsack style DP uses dp[i] = max(dp[i], j * dp[i-j]) [OK]

Hint: Unbounded knapsack uses dp[i] = max(dp[i], j * dp[i-j]) [OK]

Common Mistakes:

• Using greedy approach
• Not adjusting DP recurrence for reuse