Step-by-Step Guide: Dynamic Programming for Subset Sum Problem (Part 1)

When I study competitive programming, I feel dynamic programming is the most difficult part as a beginner.

I will explain this algorithm by showing examples with many figures. Please note that in this story, reasons why dynamic programming is better than naive approaches will not be mentioned.

Contents

Part 1 will cover 1, 2 and 3. Part 2 will cover 4 and 5.

1. Given a set of positive integers and a value sum, check if there is a subset of the given set whose sum is equal to the given sum.
2. Given a set of positive integers and a value sum, check how many subsets of the given set whose sum is equal to the given sum.
3. Given a set of positive integers and a value sum, check the minimum number of integers in the subset whose sum is equal to the given sum.
4. Given a set of positive integers and a value sum, check if there is a subset of the given set whose sum is equal to the given sum. Additional condition: Each positive integer pᵢ can be used multiple times.
5. Given a set of positive integers and a value sum, check if there is a subset of the given set whose sum is equal to the given sum. Additional condition: Each positive integer pᵢ can be used at most mᵢ times.

Problem 1

Problem Description

Given a set of N positive integers pᵢ (i = 1, …, N) and a value sum S, check if there is a subset of the given set whose sum is equal to the given sum.

Example

I will use an example to show how dynamic programming works.

N = 5, S = 12
p₁ = 5, p₂ = 11, p₃ = 3, p₄ = 4, p₅ = 7

Correct answer: True (There is at least one subset whose sum is equal to S.)

Code

import numpy as np

N = 5
S = 12
P = [0, 5, 11, 3, 4, 7] # 0th element is dummy (= not choosing any item).

# dp[i][j] := using the first i items, whether or not we can make the sum j.
dp = np.zeros((N + 1, S + 1), dtype=bool)
# Initialize. We can make the sum 0 by not choosing any item.
dp[0][0] = True

for i in range(1, N + 1):
    for j in range(S + 1):
        # Condition 1: If we can make the sum j using the first i - 1 items, we can make the sum j without the i-th item.
        if dp[i - 1][j]:
            dp[i][j] = True
        # Condition 2: If we can make the sum j - P[i] using the first i - 1 items, we can make the sum j by adding the i-th item.
        if j >= P[i] and dp[i - 1][j - P[i]]:
            dp[i][j] = True

# Show the result
print(f"Answer: {dp[N][S]}")

If you understand how the code works, you can skip to Problem 2. If you wonder why this code can solve the problem, let’s look more closely.

Step-by-Step Guide

The variable dp works as a table storing results, and looks like this below.

Beginning

Each item dp[i][j] has a boolean value (T or F), meaning whether we can make the sum j, using the first i items. In this example, N = 5 and S = 12, so the value of dp[5][12] is the answer. (Another example, if N = 5 and S = 9, the answer is dp[5][9].)

Note that the index in Python starts with 0, but the 0-th item means “not choosing any integer”. Hence the i-th in Python corresponds to the i-th in daily life. (e.g. The “1st” item in Python is 5.)

Now we start updating dp. Again, the 0th row means the state “not choosing any integer”. Therefore, dp[0][0] (= when S = 0) is True, while dp[0][j], where j is not equal to 0, is False. This is because we can’t make any positive sum by adding no integers.

Then the dp is like this below.

i = 0

Next, let’s see how dp works if we have the 1st item, 5. (Remember i = 1 now.)

If j = 0, we can make S equal to 0 by choosing “not to add 5”.

i = 1, j = 0

If 1 ≤ j ≤ 4, we can’t add 5 because the sum becomes over 5 once 5 is added. However, we can’t make j by not adding 5 either. As a result, dp[1][j] , where 1 ≤ j ≤ 4, becomes False.

i = 1, 1 ≤ j ≤ 4

If j = 5, we know it’s possible by simply adding 5.

To undetstand how the code works, the point is the blue circle in the table below. As dp[0][0] = True(the sum can be 0 by not choosing any integer), dp[1][5] = True (the sum can be 5 by adding 5 to 0). In other words, if dp[i — 1][j — 5] = True , then dp[i][j] = True.

i = 1, j = 5

If j ≥ 6, 5 is too small to make the sum large enough, so all values are False.

i = 1, j ≥ 6

Now let’s move to i = 2.

If j < 11, we can make j = 0 and j = 5 by not using 11. Hence dp[2][0]and dp[2][5]are True, while the others are False.

i = 2, j < 11

If j = 11, the sum can be 11 by choosing 11 and not choosing 5. Therefore dp[2][11]is True.

If j = 12, as you easily know, we can’t make it in the case where only 5 and 11 are available.

i = 2, j ≥ 11

We can fill out the 3rd row (i = 3) of this table in the same way. The only notable part is that we can make 8 by adding 5 and 3.

i = 3

As we have seen i ≤ 3, i = 4 and i = 5 will be nothing special for you.

The answer is dp[5][12], which is True.

i = 4 and 5

Conversion from Idea to Code

Simply speaking, there are only two conditions for dp[i][j] to be True.

Condition 1: We can make j without the i-th item (= vertical arrow in the table)
Condition 2: We can make j with the i-th item (= diagonal arrow in the table)

Therefore, we can write in this way.

Condition 1: dp[i-1][j]is True.
Condition 2: dp[i-1][j — P[i]]is True. (Note: j — P[i] ≥ 0)

This is exactly the logic in the code shown at the beginning of this section.

Additional Comment About Code

If you want to make this code a little bit shorter, this is a shorter and still readable way.

for i in range(1, N + 1):
    for j in range(S + 1):
        dp[i][j] = dp[i - 1][j] or (j >= P[i] and dp[i - 1][j - P[i]])

Problem 2

Problem Description

Given a set of N positive integers pᵢ (i = 1, …, N) and a value sum S, check how many subsets of the given set whose sum is equal to the given sum.

Example

Please note that p has been updated.

N = 5, S = 12
p₁ = 5, p₂ = 3, p₃ = 4, p₄ = 7, p₅ = 2

Correct answer: 3 (There are 3 subsets whose sum is equal to S.)

Code

import numpy as np

N = 5
S = 12
P = [0, 5, 11, 3, 4, 7] # 0th element is dummy (= not choosing any item).

# dp[i][j] := using the first i items, how many subsets are possible.
dp = np.zeros((N + 1, S + 1), dtype=np.int8)
# Initialize. We can make the sum 0 by not choosing any item.
dp[0][0] = 1

for i in range(1, N + 1):
    for j in range(S + 1):
        dp[i][j] = dp[i - 1][j] + (dp[i - 1][j - P[i]] if j >= P[i] else 0)

print(f"Answer: {dp[N][S]}")

The main difference between Problem 1 and Problem 2 is that dp for Problem 1 is bool, but dp for Problem 2 is int so that we can count the number of possible subsets.

Step-by-Step Guide

If i ≤ 1, we have at most 1 integer, so the table looks the same as Problem 1’s. The only difference is T and F are converted into 1 and 0, respectively.

i ≤ 1

This applies to i = 2 and i = 3 too because for each i there is only zero or one subset whose sum is equal to j. (The integers in P have changed, though.)

i = 2 and 3

If i = 4, we have a new value 2, which means there are two subsets for dp[i][j] if j = 7 and j = 12.

We talk a close look at j = 7 (and i = 4).

As we saw in Problem 1, for each i and j, we only have two choices: add i or not add i. And if i = 4, both choices can make j = 7.

Choice 1: dp[3][7]=1and we choose not to add 7, which makes dp[4][7]+=1. The subset is {p₂, p₃} = {3, 4}.
Choice 2: dp[4][0]=1and we choose to add 7, which makes dp[4][7]+=1. The subset is {p₄} = {7}.

To generalize this, dp[4][7] = dp[3][7] + dp[4][0] = (# patterns for Choice 1) + (# patterns for Choice 2).

i = 4

We finally come to i = 5 (p₅ = 2). Now there are many 3’s, but let’s focus on dp[5][12] as it’s the answer to this problem.

Why is it 3? This is because…

Choice 1: dp[4][12]=2, so if we don’t add p₅, there are two subsets to make j equal to 12.
Choice 2: dp[5][10]=1, so if we add p₅, there are one subset to make j equal to 12.

Therefore, the answer is 1 + 2 = 3.

Additional Comment About Code

We can write the code in this way too.

You may have to know how and works in Python.

The code value1 and value2returns value2 if value1is a truthy value and returns value1 if value1is a falsy value.

False is treated as an integer value 0.

for i in range(1, N + 1):
    for j in range(S + 1):
        dp[i][j] = (dp[i - 1][j]) + (j >= P[i] and dp[i - 1][j - P[i]])

Problem 3

Problem Description

Given a set of N positive integers pᵢ (i = 1, …, N) and a value sum S, check the minimum number of integers in the subset whose sum is equal to the given sum.

Example

The example is the same as Problem 2.

N = 5, S = 12
p₁ = 5, p₂ = 3, p₃ = 4, p₄ = 7, p₅ = 2

Correct answer: 2 (We need at least 2 integers to create a subset whose sum is equal to S.)

Code

import numpy as np

N = 5
S = 12
P = [0, 5, 3, 4, 7, 2] # 0th element is dummy (= not choosing any item).

# dp[i][j] := using the first i items, the minimum number of items required to create a subset.
dp = np.zeros((N + 1, S + 1))
dp.fill(np.inf)
# Initialize. We can make the sum 0 by not choosing any item.
dp[0][0] = 0

for i in range(1, N + 1):
    for j in range(S + 1):
        if j >= P[i]:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - P[i]] + 1)
        else:
            dp[i][j] = dp[i - 1][j]
print(f"Answer: {int(dp[N][S])}")

Step-by-Step Guide

This time the table looks different because all elements except j = 0 are filled with inf. In this context, inf means no matter which items you use, it’s impossible to create a subset whose sum is equal to j.

i = 0

Now let’s see the case where i = 1 and 0 ≤ j ≤ 4. Since j is too small to add 5, we simply copy the values for i = 0.

We can create a subset whose sum is 0 by not choosing 5, so dp[i][0] = 0.

We can't create a subset whose sum is 1, 2, 3 or 4 by not choosing 5, so dp[i][j] = inf, where j is between 1 and 4.

i = 1, 0 ≤ j ≤ 4

If j = 5, we see an integer in dp.

Vertical (not adding 5): We can’t make a subset whose sum is 5.
Diagonal (adding 5): We can make a subset whose sum is 5. The subset size of dp[0][0] is 0 (empty), and after adding 5, the size becomes 1.

As a result, dp[1][5] = 1.

i = 1, j = 5

To generalize this, we can say the value of dp[i][j] is the smaller value of these two: dp[i-1][j] and dp[i-1][j-P[i]] + 1. Again, +1 at the end of dp[i-1][j-P[i]] + 1 means we add the i-th item to a subset.

In the end, dp will be like this below.

i ≤ 5

I will add some explanations how values for j = 12 change. When we have 5 and 3, we can create 8 (dp[2][8]=2), but there is no way to create 12 (dp[2][12]=inf). 12 is too big!

Then, by adding 4, the subset becomes {5, 3, 4}, whose sum is 12, so dp[3][12] = 3.

If i = 4, we find a better way to create a subset, which is {5, 7}, so dp[4][12] = 2.

Thank you for reading until here. Please check out Part 2 too!