, I will present a solution to the Subset Sum Problem, which has linear time complexity O(n), if all the ‘n’ input values are “close enough” to each other. We will see shortly what that condition actually means, as well as why it might often be kept (or almost kept) in practice. For the inputs that are “almost close” to each other, the algorithm still has a certain probability of working fast enough.
This article is organized in the following way:
- In chapter 1, we will recall the Subset sum problem and show probably the most trivial solution to it, based on the brute-force technique.
- Chapter 2 recalls the class of NP-complete problems and how the Subset sum problem is related to it.
- Chapter 3 reviews the commonly used solution based on Dynamic programming technique, and highlights why it is a pseudo-polynomial algorithm.
- In chapter 4, I will introduce the new algorithm, called “Interval-based solution”.
- Chapter 5 will show that, similarly to the Dynamic programming technique, the Interval-based algorithm can also restore the exact subset of the items that form given target sum, and not just answer if the target sum is achievable or not.
- Finally, in chapter 6, we will see why the Interval-based algorithm actually reaches linear time complexity, if all the ‘n’ input values are close enough to each other (as well as we will understand there what the “close enough” condition actually means).
1. Recalling the Subset sum problem
The definition of the Subset Sum Problem (SSP) is quite simple:
We are given ‘n’ input integers X={_x_1, _x_2, …, x__n}, and a target sum ‘q’. It is necessary to figure out if there exists such a subset ‘Y’ of those ‘n’ integers, numbers of which will sum up exactly to ‘q’. If it does, the problem might also ask to report all the numbers of the subset ‘Y’.
Here is an example of input to the SSP:
The input set ‘X’ with ‘n=8’ input values is presented on the right.
The target sum ‘q=22’ is shown on the left.
And here is its solution:
Choosing the input values 14, 2, and 6 results in the target sum ‘q’: “14+2+6=22”.
Note, there can be cases with more than one solution, for a given target sum ‘q’:
For the target sum ‘q=30’, we have two options: “2+13+15=30” and “6+24=30”.
Also, there can be cases when there is no solution at all, meaning that there is no such subset, integers of which will accumulate exactly to the given target sum ‘q’:
No subset of the input items ‘X’ will sum up to 25.
In this article, we will consider only positive input values x__i ∈ X. However, all the ideas to be presented beneath can be applied (with minor modifications) also to the case when there are negative input values as well.
In the Subset sum problem (SSP), a slight change in the input values can lead to a complete change of the answer. Like, if there are many subsets that form the target sum ‘q’, it doesn’t mean that there will be even one subset, that forms the target sum ‘q+1’. This fact also makes the SSP not an easy one to solve.
Even when there are not many input numbers, it might still be difficult to solve the problem on a piece of paper. Often, we will need to consider all different subsets and check which one of them accumulates towards ‘q’. That approach lies in the trivial solution of SSP, brute-force, which just enumerates all possible subsets.
The idea for brute-force implementation is: considering that there exists such a subset Y⊆X, items of which accumulate towards ‘q’, let’s address the last input item x__n. There are two scenarios:
- either x__n participates in the result subset ‘Y’,
- or it doesn’t.
Having that said, if x__n does participate in ‘Y’ (x__n∈Y), then we should continue searching for such a subset from the reduced set of numbers “X \ {x__n} = {x_1, x_2, …, x__n-1}”, which will accumulate now to “q–x__n”:
While summing up ‘q=22’, we decided to take input item ‘6’ into the result subset ‘Y’.
So, from the remaining numbers, we should build up the sum “22-6=16”.
Otherwise, if the case is that x__n doesn’t participate in ‘Y’ (x__n∉Y), then we should continue searching for such a subset from the reduced set of numbers “X \ {x__n} = {_x_1, _x_2, …, _x_n-1}”, which will itself accumulate to the same target sum ‘q’:
While summing up ‘q=22’, we decided not to take input item ‘6’ into the result subset ‘Y’.
So, from the remaining numbers, we should build up the same sum “22”.
Surely, we don’t know in advance which case is true; that’s why the brute-force algorithm just tries one case after another.
When trying to solve the reduced problem (i.e., finding a proper subset from the reduced set of numbers “X \ {x__n} = {_x_1, _x_2, …, x__n-1}”), the brute-force algorithm applies the same logic recursively. So, regardless of which branch we took, next, the value x__n-1 will be considered, and at first, we will look for a solution where x__n-1 does participate in the result subset, after which we’ll look for such a solution where it doesn’t.
The decision diagram for the Subset Sum Problem. We start at the rightmost state, and on every step we either take xi into the result subset (the upper branch), or we don’t take it (the lower branch). The numbers near every state show the remaining sum that is necessary to gather.
While recursion deepens, if the remaining target sum becomes zero, it means that we are currently on the proper branch, and the considered numbers already accumulate to the original target sum ‘q’.
Following the proper path (red arrows), we will eventually build the target sum ‘q=22’.
The pseudo-code of the mentioned brute-force algorithm becomes like this:
// Searches for such a subset of ‘X’ which has a sum equal
// to ‘q’, and places it into ‘Y’. The set ‘X’ is assumed
// to have ‘n’ integers.
procedure ssp_brute_force(
X[1..n]: set of Integers,
n: Integer,
q: Integer,
Y: Reference to set of Integers )
if q==0 then
// By picking the proper integers into ‘Y’, we have
// iteratively reduced ‘q’ to zero, so the solution
// subset is already in ‘Y’.
print Y
return // No need to do anything else in this branch
if n==0 then
// ‘q’ is not zero, while the input set ‘X’ is
// exhausted. This branch didn’t led to a solution.
return
// Try with ‘X[n]’ in the solution subset
place X[n] into Y
ssp_brute_force( X\{X[n]}, n-1, q-X[n], Y )
// Continue searching with the reduced set
// (‘X’ without the last integer X[n]), for
// such a subset, which sums to ‘q-X[n]’.
remove X[n] from Y
// Try without ‘X[n]’
ssp_brute_force( X\{X[n]}, n-1, q, Y )
// Continue searching with the reduced set
// (‘X’ without the last integer X[n]), for
// such a subset, which still sums to ‘q’.
Upon the pseudo-code, we see that solving the problem for ‘n’ input items requires solving two problems, each with ‘n-1’ input items. Each of these will, in its turn, require solving two reduced problems, this time with ‘n-2’ input items, resulting overall in 4 problems with ‘n-2’ input items each. This way, the number of problems doubles on each arrival of a new input item, which makes the time complexity of the brute-force algorithm exponential – O(2_n_).
The height of the decision diagram is exponential – 2n, while its width equals ‘n’.
In practice, this algorithm can be used only if ‘n’ is sufficiently small.
However, the next algorithms for the Subset sum problem which will be described in this article, still rely on the logic of “using vs. not using” the current item.
2. Subset sum and NP-complete problems
There is a class of problems in Computer Science, called “NP-complete”, which consists of such problems that are considered difficult to solve. The described Subset Sum Problem belongs to the NP-complete class. More precisely, in order for a problem to be NP-complete, the following criteria must be met:
- It is a decision problem, meaning that for any input to the problem, the output is either “yes” or “no”.
- Regarding the Subset sum problem, any input consisting of a set of input values X = {_x_1, _x_2, …, x__n} and a target sum ‘q’ results in a “yes” or “no” answer: we either can pick a subset which accumulates towards ‘q’, or we can’t.
- When the answer is “yes”, this can be demonstrated through the existence of a short (polynomial length) solution.
- In regard to the SSP, if it is possible to pick and present such a subset Y⊆X, we can easily sum up all its integers, and check if that really equals ‘q’ or not.
- The correctness of each solution can be verified quickly (namely, in polynomial time), and a brute-force search algorithm can find a solution by trying all possible solutions.
- The brute-force solution for Subset sum problem is what we have just recalled in the previous chapter.
- The problem can be used to simulate every other problem for which we can quickly verify that a solution is correct. Hence, if we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily converted.
The last statement shows that there are also other NP-complete problems, as well as that any of them can be converted into another. So, if a polynomial-time algorithm for one NP-complete problem will be found, we could use it to solve any other NP-complete problem, by converting it to the former one. Here is a common conversion diagram between different NP-complete problems:
We see that, for example, the “Boolean formula satisfiability problem” can be converted into the “Subset sum problem”, while the latter one can be converted into the “Knapsack problem”.
3. The Dynamic programming solution of the Subset sum problem
The common solution of the Subset Sum Problem (SSP) uses a Dynamic Programming technique. The principle of any Dynamic Programming algorithm lies in initially solving problems of smaller sizes, and later using those solutions to solve the initial large problem.
Let’s “S” be a boolean matrix having dimensions “S[0..n][0..q]”, with
“S[i][p]” denoting if we can gather the sum ‘p’ by choosing only between the first ‘i’ input items.
X = {8, 4, 11, 3, 9},
q = 28.
The matrix “S” with dimensions “(n+1)*(q+1)”.
In the first chapter, we already expressed the value “S[n][q]” in a recursive way. “S[n][q]” denotes whether we can obtain the sum ‘q’ by choosing between all the ‘n’ input integers, which is the answer to the initial problem. We addressed two cases there:
- If the last item ‘x__n’ participates in the result subset ‘Y’, then we should be able to obtain the sum ‘q–x__n’, by choosing between the first ‘n-1’ input items. In other words, “S[n-1][q–x__n]” should be equal to “true”.
- Otherwise, if the last item ‘x__n’ does not participate in the result subset ‘Y’, then we should manage to obtain the target sum ‘q’ by choosing also between the first ‘n-1’ input items. In other words, “S[n-1][q]” should be equal to “true” then.
There is no third option. If either of these two conditions is satisfied, then the target sum ‘q’ is reachable. If they both are satisfied, it means that ‘q’ can be obtained both by picking ‘x__n’ and by not picking it into the result subset ‘Y’.
So the formula for the initial problem becomes:
\[\begin{equation*}
S[n][q] = S[n-1][q-x_n] \ or \ S[n-1][q]
\end{equation*}\]
And it works not only for “S[n][q]” but also for any “S[i][p]”, as the logic remains the same:
\[\begin{equation*}
S[i][p] = S[i-1][p-x_i] \ or \ S[i-1][p]
\end{equation*}\]
Now, when filling the matrix “S[0..n][0..q]”, we see that the value of any cell ‘S[i][p]’ depends only on two other cells, both situated in the row above:
Value of the cell S[3][14] (the light red one) depends only on the values of the two cells
S[2][14] and S[2][3] (the light blue ones).
This means we can calculate the matrix in top-down order, which will guarantee that at the moment “S[i][p]” is being calculated, we already know the values of both “S[i-1][p–x__i]” and “S[i-1][p]”.
The matrix will be filled in the top-down direction, calculating cells of every row from left to right.
The yellow cells are not calculated yet.
What is required to start the calculation is the content of the first row “S[0][p], p∈[0..q]”. The cell “S[0][p]” denotes if it is possible to gather sum ‘p’, having only the first 0 input items (i.e. having no item at all)”. Obviously, the answer is “false” if “p>0” and is “true” only if “p==0” (we can gather the sum 0, without using any item).
Regardless of the set of input items ‘X’, the first row of table “S” always has “S[0][0] = true”, and “S[0][p] = false”, when “p≥1”. The yellow cells are not calculated yet.
Having that said, we can calculate all cells of the table in the top-down order. For our input set, the result will be:
The last cell “S[5][28] = true”, which means that the target sum “q=28” can be obtained
by choosing between all 5 input items.
The pseudo-code of the Dynamic Programming solution becomes:
// Given an n-long set of integers ‘X’, returns if it is possible
// to find such a subset of it, which sums up to ‘q’.
function ssp_dynamic_programming(
X[1..n]: set of Integers,
n: Integer,
q: Integer ) : Boolean
S[0..n][0..q]: Matrix of Booleans
// Fill first row of ‘S’
S[0][0] := true
for p in [1..q]
S[0][p] := false
// Fill content of the matrix
for i in [1..n]
for p in [0..q]
if p < x[i]
S[i][p] := S[i-1][p]
else
S[i][p] := S[i-1][p-x[i]] or S[i-1][p]
// The answer is in the bottom-right cell
return S[n][q]
The bottom-right cell “S[n][q]” will contain the answer to the original problem, stating if we can gather the sum ‘q’ by choosing between all the ‘n’ input items.
The presented solution requires filling the matrix “S”, which has “(n+1)*(q+1)” cells. Calculating each cell is done in O(1) time. Hence, the time complexity of the Dynamic Programming algorithm becomes O(nq). This solution is called pseudo-polynomial, because here the factor ‘q’ is not proportional to any polynomial of the problem’s size. In fact, ‘q’ can be proportional even to the exponent of problem’s size.
4. Introducing the Interval-based algorithm
In the general case, the table “S” filled in the previous chapter can have quite unpredictable content at the end. However, if the input values “X = {_x_1, _x_2, …, xn}” do satisfy certain conditions, rows of the filled table might contain many adjacent cells with “true” values, as well as many adjacent cells with “false” values.
X = {9, 4, 3, 12, 5},
q = 30.
For the presented input, the last row contains one long range of true-values, starting from S[5][12] till S[5][21].
In the current row, let’s denote those adjacent cells with a value of “true” as “true-intervals”, and the adjacent cells with a value of “false” as “false-intervals”.
Some true-intervals are highlighted in green, while some false-intervals in red.
If we know in advance that the calculated table “S” will have sufficiently long true-intervals and/or sufficiently long false-intervals at the end, it will make sense to compute “S” not cell-based (as we did in the previous chapter), but interval-based.
Then, instead of representing every row as a boolean array, we will represent it as a sequence of ordered true-intervals. Within the current row, the true-intervals never intersect, so we can keep them sorted by their starting points. Also, for simplicity of the formulas to come later, when denoting a true-interval, we will mean a half-opened range [a..b). So, for example, a true-interval [5..8) will mean that on the current row, the cells 5, 6, and 7 are equal to “true”, while cell 8 is “false”.
The last row contains the following true-intervals: { [0,1), [3,6), [7,10), [12,22), [24,27), [28,31) }. All those are highlighted in green. The set of true-intervals uniquely identifies the content of the last row of the cell-based table.
Now, having the true-intervals (later denoted just as “intervals”, as false-intervals do not play a role in the algorithm to be described) of the previous row ‘i-1’, how should we compute the intervals of the current row ‘i’? Let’s recall the formula for filling the table:
\[\begin{equation*}
S[i][p] = S[i-1][p-x_i] \ or \ S[i-1][p]
\end{equation*}\]
If altering it for a moment, and assuming that there is only the second part of the OR-expression:
\[\begin{equation*}
S[i][p] = S[i-1][p]
\end{equation*}\]
it will result in all cells of the previous row being copied into the current row. In other words, for that it would be just enough to copy the intervals from row ‘i-1’ to row ‘i’.
Copying intervals from row ‘i-1’ (light green bricks) to row ‘i’ (dark green bricks).
On the other hand, if altering the formula in the other way, assuming that there is only the first part of the OR-expression:
\[\begin{equation*}
S[i][p] = S[i-1][p-x_i]
\end{equation*}\]
it will still result in copying all the cells from the previous row to the current row, but this time shifted by ‘x__i’ positions rightwards. So that is what will be necessary to do also with the intervals:
Copy-and-shifting rightwards by ‘x__i’ all the intervals from row ‘i-1’ (light green bricks) to row ‘i’ (dark green bricks).
Finally, referring to the original formula:
\[\begin{equation*}
S[i][p] = S[i-1][p-x_i] \ or \ S[i-1][p]
\end{equation*}\]
it requires us to do “OR” on the two obtained sequences of intervals, which is the same as uniting them geometrically.
Geometrically uniting the original and shifted rightwards by ‘xi’ sequences of true-intervals (first two rows) results in the sequence of true-intervals for the next item ‘xi’ (the bottom row).
Summarizing what was said above, when filling the table of true-intervals, to compute the content of row ‘i’ we should:
- shift the content of row ‘i-1’ to the right by ‘x__i’ positions, and
- unite it with the original content of row ‘i-1’.
Note, this also means that the span of row ‘i’ (right endpoint of the right-most interval) will always be by ‘x__i’ units greater than the span of row ‘i-1’.
Spans of rows grow by sizes, equal to values ‘xi’. Span of row “x1=9” is “9”. Span of row “x2=4” is “9+4=13”. Span of row “x3=3” is “9+4+3=16”, and so on.
So the span of any row ‘i’ can be calculated as:
\[\begin{equation*}
span(i) = 1 + x_1 + x_2 + … + x_i = 1 + \sum_{k=1}^i x_k
\end{equation*}\]
where the free term “1” comes because of all the intervals being half-open (the initial interval at row 0 is [0, 1), so “span(0) = 1”).
Considering that the previous row ‘i-1’ has ‘c’ intervals, shifting them all by x__i will obviously require O(c) time. Calculating the union of 2 sequences, each having ‘c’ intervals, can also be performed in O(c) time if scanning both sequences from left to right
simultaneously. This means that the transition from the previous row to the current one requires O(c) time.
Assuming that the maximal number of intervals on any row is ‘c’, the time complexity for the Interval-based algorithm becomes O(nc).
The important note that we should make here is that the value ‘c’ significantly depends on the order of input values “X = {_x_1, _x_2, …, x__n}”. Here is an example with “n=5” values, which at the end produces lots of intervals in the table.
X = {6, 11, 4, 2, 5}.
The ‘n=5’ input values are considered in arbitrary order. This results in lots of short intervals in the middle of the table.
And here is the problem solved with the same set of input values “X={_x_1, _x_2, …, x__n}”, but arranged in a different order, more precisely, in ascending order.
X = {2, 4, 5, 6, 11}.
The same input set with ‘n=5’ values, but now arriving in increasing order. We see that numbers of intervals in intermediate rows are reduced significantly.
Such a behavior is quite intuitive: if we want the intervals of the current row to remain as few as possible, their span should grow as slowly as possible. And an obvious way to achieve that is to consider all the input values x__i in ascending order.
5. Restoring the exact subset of values
The Dynamic programming solution of the Subset sum problem, which we reviewed in chapter 3, not only answers if it is possible to obtain given sum ‘q’ from the input items “X = {_x_1, _x_2, …, xn}”, but also specifies the exact subset of ‘X’ (let’s denote it by ‘Y’, ‘Y⊆X’), items of which sum up to ‘q’. To retrieve ‘Y’, we must move over the table in the opposite direction – from bottom to top.
The last cell of the table “S[n][q]”, which contains the answer to the original problem, was calculated by the formula:
\[\begin{equation*}
S[n][q] = S[n-1][q-x_n] \ or \ S[n-1][q]
\end{equation*}\]
If “S[n][q]” appears to be true (meaning that the target sum ‘q’ is reachable), it means that at least one of the 2 operands of the OR-expression is also “true”. So, we can check 2 cases:
- if “S[n-1][q] == true”, it means that the target sum ‘q’ can be obtained also by choosing only between the first ‘n-1’ input items. So the last item ‘x__n’ does not participate in ‘Y’, and we can continue building ‘Y’ only from the first ‘n-1’ items.
- if “S[n-1][q–x__n] == true”, it means that the first ‘n-1’ input items participated in building the sum ‘q–x__n’, after which we added the last item ‘x__n’, and resulted with the necessary sum ‘q’. So the last item ‘x__n’ was actually used, and we must build now another target sum ‘q–x__n’, by choosing between only the first ‘n-1’ input items.
This judgement answers whether the last item ‘x__n’ participates in the target sum ‘q’. But the same logic also works for figuring out the participation of every other input item ‘x__i’, in any other target sum ‘p’. Recalling the general formula by which the entire table was filled:
\[\begin{equation*}
S[i][p] = S[i-1][p-x_i] \ or \ S[i-1][p]
\end{equation*}\]
a similar judgement can be made in the case if any “S[i][p] == true”, which will help us to understand if the item ‘x__i’ participates in making sum ‘p’, or not.
So to reconstruct the complete subset ‘Y’, we just apply this principle repeatedly. The pseudo-code of retrieving ‘Y’ becomes:
// Given the filled matrix ‘S’, returns an exact subset of
// the n-long set ‘X’, integers of which sum up to ‘q’.
function obtain_subset(
X[1..n]: set of Integers,
n: Integer,
q: Integer,
S[0..n][0..q]: Matrix of Booleans ) : Set of Integers
if S[n][q] == false then
return ∅ // ‘q’ can’t be obtained
Y := empty set of Integers
while n > 0
// Here we know that “S[n][q]” is always true
if S[n-1][q] == true then
// Item ‘x[n]’ can be not used in ‘Y’
else
// Item ‘x[n]’ should be used in ‘Y’
insert X[n] into Y
q := q-X[n] // Remains to build the sum ‘q-X[n]’
// Move upwards to the preceding item
n := n-1
return Y
Time complexity of this function is O(n), as on every iteration we move upwards by one row over the table, while its height is ’n+1’.
In our example, reconstructing the result subset ‘Y’ is performed by the following path:
X = {9, 4, 3, 12, 5},
q = 30.
Step 1: Here we have ‘S[n][q] = S[5][30] = true’ (rightmost green circle), which means that the target sum ‘q=30’ is reachable. We see that ‘S[4][30] = false’ (blue circle above), so the sum ‘30’ can’t be obtained if choosing between the first 4 items. So, we need the item ‘x5=5’ for construction.
Step 2: It remains to construct the sum ‘30-5=25’, by choosing between the first 4 items (2nd green circle). We see that ‘S[3][25] = false’ (blue circle), which means that ‘25’ can’t be constructed if choosing only between the first 3 items. So we need to use the item ‘x4=12’.
Step 3: It remains to construct the sum ‘25-12=13’, by choosing between the first 3 items (3rd green circle). We see that ‘S[2][13] = true’ (4th green circle), which means that ‘13’ can also be gathered by choosing between only the first 2 items. That’s why we skip item ‘x3=3’.
Step 4: Now we should construct the sum ‘13’, by choosing between the first 2 items. We see that ‘S[1][13] = false’ (blue circle), which means that we can’t gather the sum ‘13’ if using only the first item ‘x1’. So we need to use ‘x2=4’ for that.
Step 5: It remains to construct the sum ‘13-4=9’, by choosing only the first input item (5th green circle). So we pick it up, as ‘x1=9’.
Can we act similarly in the Interval-based solution? We see that the only thing needed to reconstruct subset ‘Y’ in the Dynamic programming solution is knowing the value of cell “S[i][p]”, which, in relation to the Interval-based solution, is knowing whether the i-th sequence of intervals covers the coordinate ‘p’. That can be checked by running a Binary search over the current i-th sorted sequence of intervals.
The interval-based solution for the same sequence of input values X = {9, 4, 3, 12, 5}. The path to reconstruct subset ‘Y’ remains the same, and the intervals that will help in reconstruction are highlighted in yellow.
Assuming that the i-th sequence contains ‘c__i’ intervals, binary search will take O(log c__i) time. To retrieve the complete subset ‘Y’, we run binary search on each of the ‘n’ sequences of intervals. If there are at most ‘c’ intervals on each row, retrieval of the result subset ‘Y’ will run in O(n log c) time. Techniques like Fractional cascading can probably be applied here to speed up the subset retrieval process.
6. Time complexity of the Interval-based algorithm
In Chapter 4, we derived the time complexity of the Interval-based algorithm as O(nc), where ‘n’ is the number of input values and ‘c’ is the maximal number of intervals on a row. We also noted there that the order of input values “X = {_x_1, _x_2, …, xn}” matters significantly, and ‘c’ generally results in a smaller value when items of ‘X’ arrive in an increasing order. Now, are there such input cases for which the value ‘c’ will be really small?
Case 1: A geometric progression
First let’s consider the case when values of ‘X’ form a geometric progression with initial value of ‘1’ and a common ratio of ‘2’:
\[\begin{equation*}
X = \{ 1, 2, 4, 8, 16, …, 2^{n-1} \} : x_i = 2^{i-1}
\end{equation*}\]
What shape will have the set of constructed intervals?
As we already know, having intervals of the previous row ‘i-1’, to calculate intervals of the current row ‘i’, there are 2 steps:
- offset all intervals of row ‘i-1’ by ‘x__i’ to the right,
- unite the offsets with original content of row ‘i-1’.
Doing that on the mentioned input will result in:
- row 0 always has only one interval [0, 1), stating that only the sum ‘0’ is achievable if using no input item at all.
- as ‘_x_1=1’, the shifted interval becomes “[0,1) >> 1 = [1,2)”, and after uniting with the original one we have: “[0,1) ꓴ [1,2) = [0,2)”,
- as ‘_x_2=2’, the shifted interval becomes “[0,2) >> 2 = [2,4)”, and after uniting with the original one we have: “[0,2) ꓴ [2,4) = [0,4)”,
- as ‘_x_3=4’, the shifted interval becomes “[0,4) >> 4 = [4,8)”, and after uniting with the original one we have: “[0,4) ꓴ [4,8) = [0,8)”,
- and so on…
We see that each row ‘i’ has just 1 interval: [0,2_i_).
X = {1, 2, 4, 8, 16, …}
If the input values of ‘X’ form the geometric progression X = {1, 2, 4, 8, 16, …}, every row of the table will have just one interval.
Of course, the presented case is very special, and it is not a surprise that any target sum ‘q ∈ [0, 2_n_)’ can be constructed from those ‘n’ numbers. If representing ‘q’ in the binary numeral positional system, then its ‘1’ digits will correspond to the powers of ‘2’ (the input values), which should be added up to get ‘q’.
Case 2: Slower than a geometric progression
Values grow rapidly in any geometric progression. In the previous case, as the common ratio was equal to 2, we could also express every value ‘x__i’ as the sum of all previous values, plus 1:
\[\begin{equation*}
x_i = 1 + \sum_{k=1}^{i-1} x_k
\end{equation*}\]
What if the sequence ‘X’ grows more slowly? In other words, what if after sorting all values of ‘X’ in an increasing order, each value ‘x__i’ turns out less than or equal to the sum of all previous values, plus 1?
\[\begin{equation*}
\hspace{1cm} x_i \leq 1 + \sum_{k=1}^{i-1} x_k \hspace{1cm} (1)
\end{equation*}\]
To understand how the intervals will be derived in such a case, let’s recall from Chapter 4 that the span of row ‘i’ equals the sum of all previous and the current input values, plus 1:
\[\begin{equation*}
span(i) = 1 + \sum_{k=1}^{i} x_k
\end{equation*}\]
Now, if every value ‘x__i’ is less than or equal to the sum of all previous values, it means that ‘xi’ is also less than the span of its previous row:
\[\begin{equation*}
x_i \leq 1 + \sum_{k=1}^{i-1} x_k = span(i-1)
\end{equation*}\]
which means that if there is only one interval at row ‘i-1’, uniting it with its offset rightwards by ‘x__i’, will still result in only one interval at row ‘i’. Initially, we have only one interval in row ‘i=0’. So, in the case when input values grow more slowly than the mentioned geometric progression (1), each row of the table will have only one interval.
X = {1, 2, 3, 6, 11, 20},
When the input values grow slower than the geometric progression with a common ratio of ‘2’, we still have only one interval per row.
Concluding this case, if after sorting all the input values of ‘X’ increasingly, we have the constraint:
\[\begin{equation*}
x_i \leq 1 + \sum_{k=1}^{i-1} x_k
\end{equation*}\]
the table will have only “c=1” interval at every row, and the Interval-based algorithm itself will run in guaranteed O(n) time. Let’s note that from the practical perspective, such a constraint might often be satisfied. If the input data comes in random order, then an additional O(n log n) time will be required to sort it.
Case 3: Almost slower than a geometric progression
Let’s generalize the previous case 2, which had the constraint:
\[\begin{equation*}
x_i \leq 1 + \sum_{k=1}^{i-1} x_k
\end{equation*}\]
Now we will allow for it to be violated from time to time.
Once that happens for some ‘x__i’, we can expect that the number of intervals ‘c’ in row ‘i’ will become greater. But how long can ‘c’ grow? Let’s observe it on the following example:
n = 7,
X = { 1, 2, 5, 7, 10, 28, 30 },
It will be easier for us to write down another array ‘XP’, where ‘xpi’ is equal to the sum of all preceding values:
XP = { 0, 1, 3, 8, 15, 25, 53, 83 }
… we see that the mentioned condition is violated at the input values ‘_x_3=5’ (as ‘_x_3>_xp_3+1’) and ‘_x_6=28’ (as ‘_x_6>_xp_6+1’).
Now let’s construct the intervals. This time, as the span of all the inputs is large (“span(n) = 83+1 = 84”), for the last 2 rows, we will write down the sequences of intervals, instead of presenting them geometrically:
As we can see, if for some ‘x__i’ the mentioned condition is violated, the number of intervals is doubled on that row. In our example, that took place for input values ‘_x_3’ and ‘_x_6’. It happens because all the shifted intervals appear rightwards from the span of the current intervals:
If the current item xi is greater than the sum of all previous items plus 1, its shifted intervals (top-right sequence) will not have any common point with the current intervals (top-left sequence), which is why after uniting those two sequences, the number of intervals will be doubled (bottom sequence).
However, on the other rows, the number of intervals tends not to increase much, because many of them, after being united with the current row’s content, just turn into one long interval. In our example, that explicitly happened at the last row ‘_x_7=30’.
If the current item xi is less than or equal to the sum of all previous items plus 1, its shifted intervals (top-right sequence) might have many common fragments with the current intervals (top-left sequence), which is why after uniting those two sequences (the bottom sequence), lots of intervals might be merged into one. Here 6 intervals are being merged into one long interval at the bottom-center.
The naming of this article comes from the fact that if all input items “X = {_x_1, _x_2, …, x__n}” are close enough to each other, many intervals will tend to unite during the top-down construction of the table, so the constant ‘c’ might remain bounded with certain probability. If that is the case, we will end up with “O(nc) = O(n)” linear time solution for the Subset Sum Problem, assuming that the input values arrive in a sorted way. Otherwise, the initial sorting of values of ‘X’ becomes the most time-consuming step, requiring additional “O(n log n)” time.
Case 4: Faster than a geometric progression
Let’s consider one more case, when the sorted input values
“X = {_x_1, _x_2, …, x__n}” grow faster than the mentioned geometric progression with a common ratio of 2. That will happen if every value ‘x__i’ is greater than the sum of all previous values, plus 1:
\[\begin{equation*}
\hspace{1cm} x_i > 1 + \sum_{k=1}^{i-1} x_k \hspace{1cm} (2)
\end{equation*}\]
In the previous case 3, we already noted that once it happens for some ‘x__i‘ (i.e., when ‘x__i’ appears rightwards from the span of all previous values), the number of intervals doubles, because no common fragments remain between the current and the shifted sequences of intervals.
And in the current case, when ‘X’ grows faster than a geometric progression with a common ratio of 2, it happens for every input value ‘x__i’, so the number of intervals doubles on every row, resulting in an exponential growth.
Let’s consider the following example:
n = 6,
X = { 2, 5, 9, 20, 39 }.
The array with sums of all preceding values will be:
XP = { 0, 2, 7, 16, 36, 75 }.
So we see that every item ‘x__i’ is greater than the sum of all previous items, plus 1. Constructing intervals will result in the following table:
So we see that if input values “X” have the mentioned constraint (2), proceeding with the interval-based algorithm is not the best idea, as it will result in 2_n_ short intervals at the last row, thus requiring O(2_n_) time to run. If we know in advance that this will be our case, another decision-based algorithm can be applied, which will pick a necessary subset of “X” in linear time O(n).
Conclusion
In this article, we have observed a novel approach for solving the Subset Sum Problem, called “Interval-based algorithm”. It is similar to the Dynamic Programming solution, with the difference that here we operate not on individual cells of the table, but on its continuous ranges.
We have observed 4 special distributions of input values, and proved that if the inputs are dense enough, the Interval-based algorithm runs in linear time. We have also shown that when the inputs are “almost dense”, the algorithm might still work fast enough. Similar to the Dynamic Programming solution, the Interval-based algorithm allows obtaining the exact subset, items of which sum up to the given target.
The Subset Sum Problem is one of the NP-complete problems; thus, this article highlights another special case of inputs, for which they can be solved fast enough.
I am happy that you have read till the end, and thanks for your interest!
All the used illustrations are prepared by Lilit Danielyan ( https://www.behance.net/lilitdanielyan1 ).
If you enjoyed reading, feel free to connect with me on LinkedIn, and DM to share your thoughts. I would certainly like it! ( https://www.linkedin.com/in/tigran-hayrapetyan-cs/ ).
All used images, unless otherwise noted, are designed by request of the author.
Instagram Engineering
Shopify Engineering