Subset Sum Problem

Introduction

The Subset Sum Problem (SSP) is a classic problem in computer science and combinatorial optimization. It belongs to the category of decision problems, where the task is to determine whether there exists a subset of numbers in a given set that adds up to a particular value.

This problem is particularly famous because it is a special case of the more general Knapsack Problem and is known for being NP-complete, meaning it is at least as hard as the hardest problems in the class NP.

.

Problem Definition

Determine whether there exists any non-empty subset of 𝑆 such that the sum of its elements equals 𝑇.

In other words, the goal is to find any subset 𝑆′⊂𝑆 where the sum of the elements in 𝑆’ is exactly 𝑇.

Input

• A finite set 𝑆 of 𝑛 integers
• An integer 𝑇, the target sum

Output

• True if there exists a subset of 𝑆 whose sum is equal to 𝑇.
• False otherwise

Subset Sum Problem can be solved by Naïve method, Recursive method, Dynamic Programming and Backtracking.

Here, naïve method, recursive method and dynamic programming is discussed here.

.

Example

Question – Check whether the subset S make a sum equal to T or not?
Let S = {2, 4, 5, 7}
1. T = 8
2. T = 9

.
Answer – With using naive approach, we can say that
1. T is not equal to 8, because there is no subset of the set S that can create the sum 8.
2. T is equal to 9, because the subsets {4, 5} and {2, 7} can create the sum 9.

However, the naive method is quite complex. It’s feasible for simpler and smaller inputs, but not for larger ones due to its complexity of n.2ⁿ, which can complicate matters significantly.

When employing this approach to solve the Subset Sum problem for a set 𝑆 with 5 elements {0, 2, 4, 5, 7}, the method would indeed consider 2⁵=32 different possible combinations of these elements.

For each subset, we might need to sum up to 𝑛 elements. On average, the size of subsets considered is about 𝑛/2 if we consider all possible subsets uniformly. So, the final time complexity is O(n.2ⁿ).

Each combination represents a potential subset of 𝑆, and each subset’s sum is calculated to see if it matches a specific target sum. Here’s a clearer representation of how the naive method evaluates each subset

• {0, 0, 0, 0, 0} – corresponds to taking no elements, resulting in a sum of 0.
• {0, 0, 0, 0, 1} – corresponds to taking just the last element (7), so the subset sum is 7.
• {0, 0, 0, 1, 0} – takes only the fourth element (5), making the subset sum 5.
• {0, 0, 0, 1, 1} – takes the fourth and fifth elements (5 and 7), resulting in a sum of 12.
• … and so forth, up to
• {1, 1, 1, 1, 1} – takes all elements, adding up to 18 (0+2+4+5+7).

.

Recursive Algorithm

In the recursive approach, at each step, we have two choices, include the current element in the subset or exclude it. This results in a binary tree-like recursive exploration of all possible subsets.

Let’s denote the number of elements in the input set as n.

In the worst-case scenario, the recursion explores all possible subsets, which is 2ⁿ, because at each step, there are two recursive calls – one including the current element and one excluding it.

Therefore, the time complexity of the recursive algorithm for the Subset Sum Problem is O(2ⁿ).

In 1974, Horowitz and Sahni published an improved exponential-time approach that runs in time O(2^n/2. (n/2)) but takes significantly more space O(2^n/2).

In 1981, Schroeppel and Shamir published an approach based on Horowitz and Sanhi that required comparable runtime O(2^n/2. (n/4)) but significantly less space O(2^n/4).

.

Historical Context

The phrase “Subset Sum Problem” may have originated with the advent of complexity theory and computational complexity classes in the 1970s.

Richard Karp’s influential 1972 paper, “Reducibility Among Combinatorial Problems,” included the Subset Sum Problem as one of 21 NP-complete problems, which was a crucial milestone in bringing it into the spotlight of computational theory.

In the early 1970s, academics like as Stephen Cook and Leonid Levin developed and formalized complexity theory and NP-completeness, which helped to create and name norms for many computer issues, including the Subset Sum Problem.

.

Dynamic Programming comes into play

Dynamic programming offers a more efficient solution compared to naive method and recursive method, especially for larger input sizes, making it a powerful technique for solving the Subset Sum Problem.

The dynamic programming solution to Subset Sum runs in pseudo-polynomial time. This complexity is considered pseudo-polynomial because while it is polynomial in the numeric value of the target sum t and the number n, it is not polynomial in the size of the input if t is large. This is because the input size in bits is proportional to log(t), and the complexity O(n * t) can be exponential in terms of the number of bits used to represent t.

The Subset Sum problem is NP-complete, a classification in computational complexity theory. This means two things –

NP (Non-deterministic Polynomial time) – It is easy to verify a correct solution to the problem in polynomial time.

NP-complete – It is as hard as the hardest problems in NP, and no polynomial-time algorithm is known for solving all NP-complete problems efficiently.

.

Algorithm for SSP by Dynamic Programming

1. Create a 2D array (n+1)(t+1) where Array[i][j] will be True if a subset of the first i items from S can sum to j. Otherwise, it will be False.
2. Array[0][0] is True because a subset of zero elements can sum to 0.
3. Array[i][0] is True for all i, because with any number of items you can always form the sum 0 by not taking any items.
4. Array[0][j] is False for all j>0, because no subset of zero items can sum to a positive j.
5. Iterate over each item i from 1 to n (number of elements in S).
6. For each item, iterate over possible sums j from 1 to T.
7. Set Array[i][j] to True if either Array[i-1][j] is True (not taking the current item) or Array[i-1][j – S[i-1]] is True (taking the current item, hence subtracting its value from j).
8. The value at Array[n][T] will indicate whether a subset of S can sum to T.

.

Example

We use the same question that we took earlier in the  method.

Let S = {2, 4, 5, 7} and T = 9

The length of S is n = 4

Step 1 – Create a 2D array of (n+1)(t+1).

.

Step 2 – True – 1, False – 0

• Array[0][0] is True because a subset of zero elements can sum to 0.
• Array[i][0] is True for all i, because with any number of items you can always form the sum 0 by not taking any items.
• Array[0][j] is False for all j>0, because no subset of zero items can sum to a positive j.

.

Step 3 – The current item is 2, So it cannot be equal to 1. So, it is false.

.

Step 4 – The current item is 2 and the sum is also 2. So, it is true.

.

Step 5 – We only have the number 2 available, so it’s not possible for it to be greater than 2. Therefore, sums from 3 to 9 are impossible and would be false.

.

Step 6 – We have the numbers 2 and 4, with 4 being greater than 2. Therefore, for the sum equal to 4, the value can be true, but for sums less than 4, the values remain the same as in the previous row.

.

Step 7 – We have the numbers 2 and 4. Their combined sum is 6, which means it’s not possible to reach a sum of 5, but it is possible to achieve a sum of 6.

.

Step 8 – We only have the number 2 and 4 available, so it’s not possible for it to be greater than 6. Therefore, sums from 7 to 9 are impossible and would be false.

.

Step 9 – We have the numbers 2, 4 and 5 available, with 5 being greater than 2 and 4. Therefore, for the sum equal to 5, the value can be true, but for sums less than 5, the values remain the same as in the previous row.

.

Step 10 – In the previous row, sum = 6 is true, then in this current row, the sum = 6 has to be true.

.

Step 11 – The number 5 + 2 is 7. So, the sum = 7 is true.

.

Step 12 – We have numbers 2, 4 and 5. It cannot be equal to 8. So, sum = 8 is false.

.

Step 13 – The number 5 + 4 is 9. So, the sum = 9 is true.

.

Step 14 – We have the numbers 2, 4, 5 and 7 available, with 7 being greater than 2, 4 and 5. Therefore, for the sum equal to 7, the value can be true, but for sums less than 7, the values remain the same as in the previous row.

.

Step 15 – We have numbers 2, 4, 5 and 7. It cannot be equal to 8. So, sum = 8 is false.

.

Step 16 – We can sum the numbers 4 and 5 or we can sum the numbers 2 and 7, their sum = 9. So, it is true.

The algorithm will find that {4,5} is a subset of Set S that adds up to 9. Thus, the output will be True.

.

Source Code of Subset Sum Problem