Design and Evaluation of Alternate Enumeration Techniques for
Subset Sum Problem
Avni Verma and Kamalakar Karlapalem
avni.verma@research.iiit.ac.in,kamal@iiit.ac.in

arXiv:1612.01693v3 [cs.DS] 12 Dec 2016

Data Science and Analytics Center (DSAC)
International Institute of Information Technology, Hyderabad, India

Abstract. The subset sum problem, also referred as SSP, is a NP-Hard computational problem. SSP
has its applications in broad domains like cryptography, number theory, operation research and complexity theory. The most famous algorithm for solving SSP is Backtracking Algorithm which has exponential time complexity. Therefore, our goal is to design and develop better alternate enumeration
techniques for faster generation of SSP solutions. Given the set of first n natural numbers which is
denoted by Xn and a target sum S, we propose various alternate enumeration techniques which find
all the subsets of Xn that add up to sum S.
In this paper, we present the mathematics behind this exponential problem. We analyze the distribution
of power set of Xn and present formulas which show definite patterns and relations among these
subsets. We introduce three major distributions for power set of Xn : Sum Distribution, Length-Sum
Distribution and Element Distribution. These distributions are prepossessing procedures for various
alternate enumeration techniques for solving SSP. We propose novel algorithms: Subset Generation
using Sum Distribution, Subset Generation using Length-Sum Distribution, Basic Bucket Algorithm,
Maximum and Minimum Frequency Driven Bucket Algorithms and Local Search using Maximal and
Minimal Subsets for enumerating SSP.
We compare the performance of these approaches against the traditional backtracking algorithm. The
efficiency and effectiveness of these algorithms are presented with the help of these experimental results.
Furthermore, we studied the over solution set of subsets generated by various algorithms to get the
complete solution for subset sum problem. Finally, we present a conjecture about upper bound on the
number of subsets that has to be enumerated to get all solutions for Subset Sum Problem.

1

Introduction

In SSP, we consider a set of n positive integers stored in set X and a target sum S. X = {x1 , x2 . . . xn }.
Traditionally, there are two definitions for SSP which are described below:
1. Version 1: Given a set X containing positive integers and a target sum S, is there a subset which sum
upto S? This is a NP-Complete problem.
For example, given X = {5, 4, 9, 11} and S = 9, the solution to this problem is true. There are many
ways to solve this problem and it depends on the size and values of X and S. The brute force algorithm
iterates through all possibilities and takes O(2n × n) time for execution. For smaller size and values of
X and S, SSP can be solved in polynomial time by using dynamic programming with time complexity
O(n × S) [19].
2. Version 2: Given a set X containing positive integers and a target sum S, find a subset which can sum
up to S. This is a NP-Hard problem.
For X = {5, 4, 9, 11} and S = 9, the solution to above problem is either {5, 4} or {9}. This is a exponential
time taking problem which can be solved in O(2n × n) time by using brute force. This method requires
O(n) storage space to store the required result. This version of SSP does not have any known polynomial
time algorithm.
In this paper, we extend the traditional SSP (Version 2) and design various alternate enumeration techniques. Instead of finding one subset with target sum, we find all possible solutions of SSP. Therefore, for
X = {5, 4, 9, 11} and S = 9, solutions to our version of SSP are {5, 4} and {9}. We further confine and
refine our problem domain by considering first n natural numbers as set X. There are many advantages
for selecting this problem domain. It simplifies the problem statement, avoids duplication and since sum of

first n natural number is n(n+1)
, by selecting X = {1, 2 . . . n} we restrict target sum between 1 and n(n+1)
,
2
2
n(n+1)
S ∈ [1, 2 ]. The efforts to solve Subset Sum Problem are required to get subset queries in relational
databases [18]. Before describing the formulation of our problem in detail we explore the research work
conducted in field of SSP.

2

Related Work

The Subset Sum Problem has been studied very widely. It has a standard O(nu) pseudo-polynomial time
dynamic programming algorithm [17] which is taught in elementary algorithms class. Additionally, there are
a number of other algorithms in the literature, including an FPTAS [10], an exact algorithm with space
and time trade offs [1], a polynomial time algorithm for most low density sums [14], and a number of more
specialized pseudo-polynomial time algorithms with various properties [12] [5] [15] [13].
There is also another variant of Subset Sum Problem which allows the elements in X to be used any
number of times in the sums. Overall, dynamic programming is expected to be most efficient for very dense
instances, while backtracking is expected to be most efficient for sparse instances of Subset Sum Problem.
In different versions of the SSP, the input set may or may not contain duplicate values, and the problem can
also be expressed as an optimization problem.
In [11], the authors have introduced a new faster pseudo-polynomial time algorithm for the Subset Sum
problem to decide if there exists√a subset of a given set S whose elements sum to a target number t. Their
proposed algorithm runs in O( nt) time, where n is the size of set S. Their approach is based on a fast
Minkowski sum calculation that exploits the structure of subset sums of small intervals.
Despite the apparent simplicity of the problem statement, to date there has been modest progress on
exact algorithms[4] for Subset Sum Problem. Indeed, from a worst-case performance perspective the fastest
n
known algorithm runs in O(2 2 ) time and dates to the 1974 work of Horowitz and Sahni[9]. Improving the
worst-case running time is a well-established open problem[20].
In [2], the authors present a randomized algorithm. They consider positive integers and a target sum but
instead of fidning all subsets of target sum, the solution is bounded by B concentration. The main result
of this algorithm is that all instances without strong additive structure (without exponential concentration
n
of sums) can be solved faster than the Horowitz-Sahni time bound O(2 2 ) [9]. They have also shown a
quantitative claim to show or prove it. Complexity of this randomized algorithms is O(20.3399n B 4 ).
Beier and Vocking [3] presented an expected polynomial time algorithm for solving random knapsack
instances. Knapsack and subset sum have similarities, but the random instances considered there are quite
different from ours, and this leads to the development of quite a different approach. Subset sum problem
is also closely related to the classical number theory study of determining partitions. In [8] Hardy and
Wright provide generating functions but is limited due to lack of computational scheme for generating such
partitions. A survey of algorithms for the different variations of the knapsack problem is given in [3]. Much
of the early work in the knapsack problem was done by Gilmore and Gomory [6] [7].
However, there is very little work done on enumeration techniques for subset sum problem, which we
addressed in this work. We have developed different algorithms for alternate enumerations techniques for
subset sum problem and have compared their performance.

3

Formulation for Subset Sum Problem

The following set of information is used for presenting the exponential aspect and solution of alternate
enumeration techniques of SSP:
1. A set of first n natural numbers. Xn = {1, 2, 3 . . . n} where n is a positive integer. The set Xn is also
known as the Universal set. This is our problem domain. The cardinality of the set Xn is n. |Xn | = n
2. A set of all subsets of Xn is P (Xn ) = {φ, {1}, {2} . . . {1, 2 . . . n}}. It is also known as power set. The empty
set is denoted as φ or {} or the null set. In this paper, we use φ for the representation. |P (Xn ) | = a = 2n
3. maxSum(n) is the sum of all elements of the universal set Xn . This is the maximum possible sum for
any element of P (Xn ).
maxSum(n) = b = (1 + 2 + 3 . . . n) = n(n+1)
.
2
n(n+1)
Sum(A) ≤ maxSum(n) =
∀A ∈ P (Xn )
2

4. Sum(A) is the sum of all elements of a set A where A belongs to power sets of Xn , A ∈ P (Xn ).
– We assume sum of all elements of φ as 0, Sum(φ) = 0.
– The range of Sum(A) is [0, n(n+1)
].
2
– The minimum possible sum for A, where A ∈ P (Xn ), is denoted as minSum(n).
5. midSum(n) is the mid point of the range of Sum(A) where A ∈ P (Xn ). Since, the maximum possible sum for power sets of Xn , P (Xn ) is n(n+1)
and minimum possible sum is 0, midSum(n) =
2
n(n+1)

0+
minSum(n)+maxSum(n)
2
=
2
2
= n(n+1)
midSum = d = (1+2+3...n)
2
4

6.

7.

8.

9.

4

For simpler calculations, we consider midSum as the largest integer less than or equal to the mid
point, f loor(midSum(n)) = b n(n+1)
c.
4
maxLength(n) is the count of all elements of the universal set Xn . This is the maximum possible length
for any element of P (Xn ).
– Therefore, maxLength(n) is equal to the cardinality of set Xn , defined in point-1.
– maxLength(n) = |Xn | = |{1, 2 . . . n}| = n
Len(A) is the count of all elements of a set A where A belongs to power sets of Xn , A ∈ P (Xn ).
– The range of Len(A) is from 1 to n, Len(A) ∈ [1, n].
– We consider, count of all elements of subset φ as 1. Len(φ) = 1.
– Therefore, the range of Len(A) is from 1 to n. Len(A) ∈ [1, n].
– The minimum possible length for A, where A ∈ P (Xn ), is denoted as minLen(n).
minSum(n, l) is the sum of a subset A where A ∈ P (Xn ) with Len(A) = l. A is the subset of length
l with minimum possible sum. Subset of length l with minimum possible sum contains first l smallest
natural numbers. Therefore, minimum possible subset of length l is A = {1, 2 . . . l}.
minSum(n, l) = (1 + 2 + . . . + l) = l(l+1)
2
maxSum(n, l) is the sum of a subset A where A ∈ P (Xn ) and Len(A) = l. A is the subset of length
l with maximum possible sum. Subset of length l with maximum possible sum will contain l largest
natural numbers decreasing from n.
– Maximum possible subset of length l is A, A = {n, n − 1 . . . n − (l − 1)}.
– maxSum(n, l) = (n + (n − 1) + . . . + n − l + 1) = n × l − l−1(l−1+1)
2
– maxSum(n, l) = l(2n−l+1)
2

Distribution Formulae

We have analyzed the distribution of P (Xn ) over sum, length and count of individual elements. We present
distribution formulas and algorithms, along with example, which show definite patterns and relations among
these subsets.
In table 1, we briefly present the formula, definition, meaning, values and assumptions of all distributions
which are required for design and evaluation of alternate enumeration techniques for SSP. Cardinality of
a set is the number of elements of the set. These distributions are prepossessing procedures which are
required for presenting our novel alternate enumeration techniques for solving SSP. The formulae are the
notation developed in Section-3. In Table 1, b denotes the maximum possible sum for any element of P (Xn ),
b = n(n+1)
.
2
Distribution
SD
SumDistribution

Formula
A 2D matrix with cardinality
n × b, where |Xn | = n and
b = n(n+1)
.
2

Meaning
SD[n][S] represents the count
of all the subsets belonging to
P (Xn ) with sum S.
Every row, SD[n], is the sum
distribution for all subsets of
Xn where sum is S.

Value/Assumption
In this thesis, the empty set
φ is counted once while calculating the sum distribution,
SD[n][0] = 1.

LD
A 3D matrix of cardinality n × LD[n][S][l]
represents
the
Length-Sum- b × n, where |Xn | = n and b = count of all the subsets belongDistribution n(n+1) .
ing to P (Xn ) with sum S and
2
length l.
Every column of this matrix,
LD[n][S][l0 ], where ∀l0 ∈ [0, n],
is the length distribution for
all subsets of Xn with sum S.
ED
A 3D matrix of cardinality n × ED[n][S][e] represents the
Elementb × n, where |Xn | = n and b = count element e in all the
Distribution n(n+1) .
subsets belonging to P (Xn )
2
with sum S.
Every row, ED[n][S], is the
element distribution for all
subsets of Xn with sum S.

Extending the previous assumptions we get,
LD[n][S][0] = 1, ∀S ∈ [0, b]
LD[n][0][l] = 1, ∀l ∈ [1, n]

In this thesis, we assume the
count of element-φ in all subsets of P (Xn ) as 0.
ED[n][S][0] = 0, ∀S ∈ [0, b]
A zero-sum is achieved only by
subset φ.
ED[n][0][e] = 0, ∀e ∈ [0, n].

Table 1: Formula, definition, meaning, values and assumptions of all distributions which are required for
design and evaluation of alternate enumeration techniques for SSP. First column denotes the distribution
name, second and third column define the formula, definition and concept behind every distribution and
fourth column states all the assumptions.

4.1

Sum Distribution

In sum distribution, also referred as SD, we find the number of subsets which sum up to a certain integer
S, where Xn = {1, 2, 3 . . . n} and S ∈ [0, n(n+1)
]. It is represented as SD[n][S]. Equation 1 establishes the
2
formula for the sum distribution. Before counting the subsets of a particular sum, we initialize the count as
zero, ∀n, S SD[n][S] = 0. Following are the base cases for sum distribution (SD[n][S]):

1. For n = 0 and S = 0, the corresponding subset is φ. Since, zero-sum (Sum = 0) can be achieved only
with subset φ and Sum(φ) is assumed to be 0, as defined in Section 3, the count of occurrence of φ-subset
in P (X0 ) is taken as 1. Therefore, SD[0][0] = 1.
2. ∀i ∈ [1, n] and S = 0, SD[i][0] = 1. Since, zero-sum (Sum = 0) can be achieved only with subset φ, the
count of occurrence of φ-subset in P (Xn ) is taken as 1. Therefore, SD[n][0] = 1.
3. SD[i][j] = 0, if i < 0 or j < 0.


1
(S = 0) or (n = 1)





0
(n = 0)



SD[n − 1][S]
0<S<n
SD[n][S] =
SD[n − 1][S] + SD[n − 1][S − n] n ≤ S ≤ b n(n+1)
c

4


n(n+1)


SD[n][maxSum(n)
−
S]
b
c
<
S
≤
maxSum(n)
=

4


0
otherwise

(1)
n(n+1)
2

Similar to Element Distribution (Section 4.3), we can give uniqueness and correctness proof of Sum Distribution.

4.2

Length-Sum Distribution

In length-sum distribution, we find the number of subsets of Xn of length l which sum up to S where
S ∈ [0, maxSum(n)], maxSum(n) = n(n+1)
and l ∈ [0, n]. Table 2 presents the bases cases for Length-Sum
2
Distribution.


1





LD[n
− 1][S][l]

LD[n][S][l] = LD[n − 1][S][l] + LD[n − 1][S − n][l − 1]



LD[n][maxSum(n) − S][n − l]



0

l = 0 and S = 0
1 ≤ l ≤ b n2 c and 0 ≤ S < n
1 ≤ l ≤ b n2 c and n ≤ S ≤ n(n+1)
2
b n2 c < l ≤ n
otherwise

(2)

Similar to Element Distribution (Section 4.3), we can give uniqueness and correctness proof of Length-Sum
Distribution.
Values Subset Sum of the Subset No. of Subsets /
of l
Length
for
Distribution
n=0
l=0
{φ}
0
1

Values Subset Sum of the Subset No. of Subsets /
of l
Length
for
Distribution
n=1
l=0
{φ}
0
1
l=1
{1}
1
1

Values Subset Sum of the Subset No. of Subsets /
of l
Length
for
Distribution
n=2
l=0
{φ}
0
1
{1}
1
1
l=1
{2}
2
1
l=2
{1, 2}
3
1

Table 2: Length-Sum Distribution for base cases: X0 , X1 and X2 . First column presents the possible length
values, second and third column presents the corresponding subsets and their sum respectively and the fourth
column presents the Length-Sum distribution, LD[n][S][l].

4.3

Element Distribution

In Section 4.1, we have explained and explored the concept of Sum Distribution, where we count the number
of subsets out of all power set P (Xn ), of Xn which add up to a certain number S. Let us assume, M
represents such sets. We study the occurrence of each element from set Xn in set M . e denotes each element
of Xn , ∀e ∈ [1, n], ∀S ∈ [0, n(n+1)
], element distribution function, ED[n][S][e], is defined as follows:
2

0
(n = 0) or (S = 0) or (e = 0)





or (0 < S < n and e == n)





ED[n
−
1][S][e]
0 ≤ S < n and 1 ≤ e < n

ED[n][S][e] = ED[n − 1][S][e] + ED[n − 1][S − n][e] n ≤ S ≤ n(n−1)
and 1 ≤ e < n and n > 2 (3)
2


n(n+1)

SD[n − 1][S − n]
n≤S≤
and e == n

2


n(n−1)
n(n+1)


SD[n][S]
−
ED[n][maxSum
−
S][e]
+
1
≤
S
≤
and 1 ≤ e < n

2
2


0
otherwise
Element distribution is another prepossessing procedure required for presenting various alternate enumeration techniques especially bucket algorithms introduced in Section 5.4.

Values for n=5
l=0
l=1
l=2
l=3
Sum Subset Size Sum Subset Size Sum Subset Size Sum Subset Size Sum
0

φ

1

1
2
3

{1}
{2}
{3}

1
1
1

3
4
5

4

{4}

1

6

5

{5}

1

7
8
9

{1, 2}
{1, 3}
{1, 4},
{2, 3}
{1, 5}
{2, 4}
{2, 5}
{3, 4}
{3, 5}
{3, 6}

1
1
2
2
2
1
1

{1,
{1,
{1,
{1,
9 {2,
{1,
10 {2,
{1,
11 {2,
12 {3,
6
7
8

2,
2,
2,
3,
3,
3,
3,
4,
4,
4,

3}
4}
5}
4}
4}
5}
5}
5}
5}
5}

10 {1, 2, 3, 4}
11 {1, 2, 3, 5}
12 {1, 2, 4, 5}

1
1
1

2

13 {1, 3, 4, 5}

1

2

14 {2, 3, 4, 5}

1

1
1
Size

{1, 2, 3, 4, 5}

15

Size

1
1
2

l=5
Subset

Sum

l=4
Subset

1

Table 3: Length-Sum Distribution for P (X5 )

Table 4 represents the count of elements in {1, 2} and {1, 2, 3} in all subsets of X2 and X3 respectively
which are divided based on their sums. These are the base cases. Similarly, Table 5 represents distribution
of elements of X5 in P (X5 ), where subsets are categorized on the basis of their Sum. Element distributions
of X0 includes the count of element 0 in subset φ with Sum = 0 . We assume ED[0][0][0] = 0. For a given
n, the count of element 0 in all the subsets is considered as N U LL or 0. We are not including 0 in the set of
first n natural numbers. This generate ED[n][S][0] = 0 ∀S ∈ [0, n(n+1)
]. Also, for any value of n, a zero-sum
2
is achieved only by subset φ which is an empty set. Therefore, ED[n][0][e] = 0 ∀e ∈ [0, n]. We consider values
of elements distribution for P (X0 ), P (X1 ) and P (X2 ) as seed values. Following are the values:
1.
2.
3.
4.
5.

ED[0][0][0] = 0
ED[1][1][1] = ED[2][1][1] = 1
ED[2][2][2] = 1
ED[2][3][1] = ED[2][3][2] = 1
otherwise ED[i][j][k] = 0

Subsets → φ {1} {2} {1, 2}
Elements ↓
1
2

0 1
0 0

0
1

1
1

Subsets → φ {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}
Elements ↓
1
2
3

0 1
0 0
0 0

0
1
0

0
0
1

1
1
0

1
0
1

0
1
1

1
1
1

Table 4: Distribution of elements [1,2] in P (X2 ) and elements [1,2,3] in P (X3 ).

Correctness of the Element Distribution Formula We present the theorems and lemma which prove
the correctness of Element distribution formula, ED[n][S][e] presented in Equation 3. ED[n][S][e] represents
the count of element e in those subsets of Xn which has sum S where e ∈ [1, n], S ∈ [0, maxSum] and
maxSum = n(n+1)
.
2
Theorem 1 ED[n][S][n] = 0 if 0 < S < n.
Proof. Let us assume ED[n][S][e] 6= 0 and ED[n][S][e] = c, where c is a positive integer. c is the count of
number of times an element e occur in a class of subsets element(n,S,e) where element(n,S,e) consist of all

No. of Subsets
for a Sum
Sum →
Integers ↓
1
2
3
4
5

Values for n=5
1112233333 3 2 2 1 1 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0
0
0
0
0

1
0
0
0
0

0
1
0
0
0

1
1
1
0
0

1
0
1
1
0

1
1
1
1
1

2
2
1
1
1

1
2
1
2
1

2
1
2
1
2

1
1
2
2
2

2
2
2
2
2

1
2
1
1
2

1
1
1
2
2

1
0
1
1
1

0
1
1
1
1

1
1
1
1
1

Table 5: Distribution of elements [1, 2, 3, 4, 5] in P (X5 ).

the subsets of P (Xn ) which add up to a sum of S. Since, c represents a count, it cannot be negative. By
definition c, ED[n][S][e] and element(n,S,e) follow these equations:
c = |element(n,S,e) |

(4)

ED[n][S][e] = |element(n,S,e) |

(5)

c = ED[n][S][e]

(6)

Let A be a subset of element(n,S,e) . Then, e will belong to A and sum of all elements of A will be greater
than or equal to e.
e∈A
(7)
Sum(A) ≥ e

(8)

S≥e

(9)

Since (e == n) as per the initial conditions, Equation 9 will become,
S≥n

(10)

Since 0 ≤ S < n it results into a contradiction. Our assumption is false. There are no subsets which contain
e and have sum less than e. Therefore, from the condition c = 0 and from Equation 9
ED[n][S][e] = 0

(11)

ED[n][S][e] = 0 if 0 < S < n and e == n

(12)

Hence, we have proved the first part of Equation 3.
Theorem 2 ED[n][S][e] = ED[n − 1][S][e] + ED[n − 1][S − n][e] if n ≤ S ≤

n(n−1)
,
2

1 ≤ e < n and n > 2.

Proof. Let element(n,S,e) be a class of subsets which consists of all the subsets of P (Xn ) which sum upto S
and contain an element e, 1 ≤ e < n. Let us assume, a set A ∈ element(n,S,e) . Since (S ≥ n), then A may
or may not contain element n. If n ∈ A then A − n belongs to the class of subsets of P (Xn−1 ) which sum
upto (S − n) and contain an element e (as presented in Equation 13). If n ∈
/ A then, A belongs to the class
of subsets of P (Xn−1 ) which sum upto S and contain an element e (as presented in Equation 14).
A − n ∈ element(n−1,S−n,e)

(13)

A ∈ element(n−1,S,e)

(14)

From Equation 13 and Equation 14, we form the set of all subsets which sum up to S and contain element
e,
element(n,S,e) = element(n−1,S,e) ∪ element(n−1,S−n,e)

n≤S≤

n(n − 1)
2

and

1≤e<n

(15)

Taking cardinality on both sides of Equation 15,
|element(n,S,e) | = |element(n−1,S,e) | + |element(n−1,S−n,e) | n ≤ S ≤

n(n − 1)
2

and

1≤e<n

n(n − 1)
and 1 ≤ e < n
2
In order to complete this proof following properties of element(n,S,e) should be proved.
ED[n][S][e] = ED[n − 1][S][e] + ED[n − 1][S − n][e] n ≤ S ≤

(16)

(17)

1. Uniqueness: There should be no duplicate subsets in element(n,S,e) , element(n−1,S,e) ∩element(n−1,S−n,e) =
φ.

Proof. element(n−1,S,e) is the set of all the subsets of P X(n−1) containing element e with sum S and
element(n−1,S−n,e) is the set of all the subsets of P X(n−1) containing element e with sum (S − n). We
use the method of contradiction to prove set of subsets in element(n−1,S,e) and element(n−1,S−n,e) are
independent. Let us assume, subset p belongs to both element(n−1,S,e) and element(n−1,S−n,e) . Since,
p ∈ element(n−1,S,e) , therefore by definition, the subset p contains element e, has elements ranging from
1 to (n − 1) and these elements sum upto S.
len(p)

S=

X

pi

(18)

i=1

Similarly, as per assumption, p ∈ element(n−1,S−n,e) . Therefore by definition, the subset p contains
element e, has elements ranging from 1 to (n − 1) and these elements sum upto (S − n).
len(p)

(S − n) =

X

pi

(19)

i=1

Plen(p)
From Equation 18 and Equation 19, there is a contradiction as i=1 pi is both S and (S − n). Since, n
is a natural number, the above equations contradict our assumption that a subset p can belong to both
sets element(n−1,S,e) and element(n−1,S−n,e) . Therefore, by contradiction, there is no subsets p which
belongs to both sets. Hence, element(n−1,S,e) and element(n−1,S−n,e) are independent.
2. Completeness: element(n,S,e) should contain all the subsets of P (Xn ) which contain element e and sum
upto S.
Proof. The power set of Xn , P (Xn ) which contain element e and sum upto S can be divided into two
parts: subsets with sum S which contain element n and subsets with sumS which do not contain element
n. By definition, element(n−1,S,e) is the set of all the subsets of P X(n−1) with sum S containing element
e and element(n−1,S−n,l−1) is the set of all the subsets of P X(n−1) with sum (S −n) containing element
e.
In Equation 15, the union of sets element(n−1,S,e) and element(n−1,S−n,e) generates all subsets of P (Xn )
with sum S containing element e. Therefore, element(n,S,e) should consists of subsets of P (Xn ) with
sum S containing element e.
The above two proofs are required to complete the statement: ED[n][S][e] = ED[n − 1][S][e] + ED[n −
and 1 ≤ e < n. This theorem will only be true, if sum is positive i.e. S ≥ 0
1][S − n][e] if n ≤ S ≤ n(n−1)
2
S≥0

(20)

n(n − 1)
−n≥0
2

(21)

n2 − n − 2n
≥0
2

(22)

n2 − 3n
≥0
2

(23)

n(n − 3)
≥0
2

(24)

n(n − 3) ≥ 0

(25)

Therefore, either both n and n − 3 should be greater than 0 or both should be less than 0. Since, n cannot
be negative,
n ≥ 0 and n ≥ 3
(26)
Therefore,
n≥3

(27)

Hence, from Equation 17 and Equation 27 we have proved the third part of Equation 3.
Lemma 3 ED[n][S][e] = ED[n − 1][S][e] if 0 ≤ S < n and 1 ≤ e < n.
Proof. According to Theorem 2,
ED[n][S][e] = ED[n − 1][S][e] + ED[n − 1][S − n][e] n ≤ S ≤

n(n − 1)
2

and

1≤e<n

(28)

Since,
0≤S<n

(29)

(−n) ≤ S − n < 0

(30)

But a sum cannot be negative. Therefore, count of element e in subsets of P (Xn−1 ) which sum up to S is
zero, ED[n − 1][S − n][e] = 0.
ED[n][S][e] = ED[n − 1][S][e] + 0
(31)
ED[n][S][e] = ED[n − 1][S][e]

0≤S<n

and

1≤e<n

(32)

Equation 32 proves the second part of Equation 3.
Theorem 4 ED[n][S][e] = SD[n − 1][S − n] if n ≤ S ≤

n(n+1)
2

and e == n.

Proof. Let element(n,S,e) be a class of subsets where it consist of all the subsets of P (Xn ) which sum up to S
and contain an element e, e == n. Let us assume A ∈ element(n,S,e) and |element(n,S,e) | = ED[n][S][e] = c
where c ≥ 0. Since, element e belongs to set A, e ∈ A,
A − e ≡ A − n ∈ element(n−1,S−e,0)

(33)

Sum S will result in following condition,
n≤S≤

0≤S−n≤

n(n + 1)
2

(34)

n(n + 1)
−n
2

(35)

Let us assume S − n as S 0 ,
0 ≤ S0 ≤

n2 − n
2

(36)

0 ≤ S0 ≤

n(n − 1)
2

maxSum(n − 1) =

(37)

n(n − 1)
2

(38)

From Equation 33 and Equation 38,
where 1 ≤ e0 < n

∀A − n ∈ element(n−1,S−n,0) ≡ element(n−1,S−n,e0 )
∀A ∈ element(n,S−n+n,n) ≡ element(n−1,S−n,e0 )
∀A ∈ element(n,S,n) ≡ element(n−1,S−n,e0 )

where 1 ≤ e0 < n

where 1 ≤ e0 < n

(39)
(40)
(41)

Taking cardinality on both sides,
|element(n,S,n) | = |element(n,S,r) | = |element(n−1,S−n,e0 ) |

(42)

ED[n][S][e == n] = ED[n − 1][S − n][e0 ]

(43)

|element(n−1,S−n,e0 ) | is the number of subsets Xn−1 which sum up to (S − n) = (S − e) = (S − n) . By using
the concept of sum distribution defined in Section 4.1 and Equation 43,
|element(n−1,S 0 ,e0 ) | = SD[n − 1][S − n]

(44)

ED[n − 1][S 0 ][e0 ] = ED[n][S][e == n] = SD[n − 1][S − n]

(45)

ED[n][S][e] = SD[n − 1][S − n] where

n≤S≤

n(n + 1)
2

and

e == n

(46)

Equation 46 proves the fourth part of Equation 3.
Theorem 5 ED[n][S][e] = SD[n][S]−ED[n][maxSum(n)−S][e] if ( n(n−1)
+1) ≤ S ≤
2

n(n+1)
2

and 1 ≤ e < n

Proof. maxSum(n) is the sum of all elements of Xn = 1 + 2 + . . . n = n(n+1)
, as defined in Section 3. Let
2
us assume S 0 = maxSum(n) − S. Since, the plot between number of subsets and sum follow a Gaussian
symmetric distribution, SD[n][S] will be equal to SD[n][maxSum(n) − S].
SD[n][S] = SD[n][S 0 ] = c

(47)

There are c number of subsets which sum up to S and S 0 . In this case, sum S is greater than the maxSum
2
(the mid point) and by using the reflection/symmetric property of the curve we can find all the values of
ED[n][S][e].
maxSum
n(n + 1)
S 00 =
=
(48)
2
4
Slow =
Slow − S 00 =

n(n − 1)
+1
2

(49)

n(n − 1)
n(n + 1)
+1−
2
4

(50)

n(2n − 2 − n + 1)
+1
2

(51)

Slow − S 00 =

f (n) = Slow − S 00 =

n2 − 3n + 2
2

(52)

By using the property of second derivative test we show that f 0 (n) is greater than 0 when S >
d(f (n))
>0
dn

(53)

d(n2 − 3n + 2/2)
>0
dn

(54)

f 0 (n) =

f 0 (n) =

maxSum
.
2

f 0 (n) = n −

3
>0
2

(55)

3
(56)
2
Therefore, ∀n ≥ 2 we can use the symmetric property and calculate half of the values by using the previously
calculated values. For n = 1 values of element distribution will be covered as the part of base cases.
Let sum(n,S) be a set of all the subsets of P (Xn ) which sum up to S and sum(n,S 0 ) consist of all subsets of
P (Xn ) which sum to S 0 , where S 0 = (maxSum − S). ∀A ∈ sum(n,S) and Ac ∈ sum(n,S 0 ) where Ac is the
complement set of A.
A ∪ Ac = U
(57)
f 0 (n) = n >

Since, U is the universal set, U = {1, 2 . . . n} and contain a single occurrence of each element e ∈ [1, n],
therefore, A ∪ Ac also contains a single occurrence of each element e. From Equation 57 there are c subsets
in A and Ac . ∀k ∈ [1, n] count of e in A and Ac is 1. Let us define Count(x, y) as the count of element x in
any subset or class of subsets y.
Count(e, A) + Count(e, Ac ) = 1
(58)
∀e ∈ [1, n], ∀A ∈ sum(n,S) and ∀Ac ∈ sum(n,S 0 )
Count(e, sum(n,S) ) + Count(e, sum(n,S 0 ) ) = |sum(n,S) | ∗ 1 = |sum(n,S 0 ) | ∗ 1

(59)

By using the definition of element distribution and Equation 47
ED[n][S][e] + ED[n][S 0 ][e] = c

(60)

ED[n][S][e] + ED[n][S 0 ][e] = SD[n][S]

(61)

ED[n][S][e] = SD[n][S] − ED[n][S 0 ][e]

(62)

Therefore, by putting the value of S 0 = (maxSum(n) − S)
ED[n][S][e] = SD[n][S] − ED[n][maxSum(n) − S][e]

(63)

Equation 63 proves the last part of Equation 3.
Sum Distribution, Length-Sum Distribution and Element Distribution are used in developing alternate
enumeration techniques for solving SSP. These techniques are presented in the next section.

5

Alternate Enumeration Techniques for Subset Sum Problem

In this paper, we propose seven approaches to find the solution for enumerating all the (2n − 1) subsets
of Xn . In each approach, we choose different method for addressing the enumeration of SSP. We propose
novel algorithms: Subset Generation using Sum Distribution (SDG), Subset Generation using Length-Sum
Distribution (LDG), Basic Bucket Algorithm (Basic BA), Maximum and Minimum Frequency Driven Bucket
Algorithms (Max FD and Min FD) and Local Search using Maximal and Minimal Subsets (LS MaxS and
LS MinS) for enumerating SSP. The first approach is the backtracking algorithm. It is the naive method for
solving SSP. This algorithm is used to benchmark the new proposed algorithms.

5.1

Subset Generation using Backtracking

Our aim is to find all the subsets of set Xn with Sum = S. According to the exhaustive search algorithm
for SSP [19], we try to find the resulting subset by iterating through all possible 2n solutions. But in this
algorithm, we arrange the elements in an orderly fashion. The worst case time complexity for this algorithm
is exponential. It is O(n × 2n ). The space complexity for this algorithm is the size of the input, O(n). Even
though backtracking is a clean and crisp algorithm for SSP, this algorithm has many drawbacks. It tries
to generate all the desired subsets by checking every branch and subset. Since there can be a lot of high
branches at every state of the back tracking algorithm, this leads to inefficient, multiple recursive calls and
reversion to old states. It requires a large amount of time and space to reflect the changes in the system
stack.
5.2

Subset Generation using Sum Distribution

We design a generator using Sum Distribution. Algorithm 1 is the pseudo-code for generating all the subsets
of Xn with sum S. As we know, sum distribution is recursive and uses subsets of X(n−1) to produce results
for Xn . We store these previous values with the help of SDG (initialized at Line 1). Extra values of SDG
(SDG[i − 1]) are freed in Line 20 to minimize the space consumption. In Line 2, we iterate through smaller
natural numbers. Line 3 to Line 6 define start sum, mid sum, end sum and universal set. Line 7 to Line
19 iterate through values of sum between start sum and mid sum. The desired set of subsets, SDG[i][j]
(subsets of Xi with sum j), consists of all subsets of SDG[i − 1][j] and SDG[i − 1][j − i]. Next, we include
ith element in every subset of SDG[i − 1][j − i]. For each of these resulting subsets, a symmetric subset of
sum (end sum − j) is calculated by subtracting the subset from universal set. Line 11 to Line 18 essentially
execute these steps and returns the final result at Line 22.
−3
The value of maximum number of subsets has exponential bound, O(2n ∗ n 2 ), as described in Appendix
−3
7. Therefore, the time complexity for (loop3 ) at Line 14 is O(2n ∗ n 2 ). Since, n ∈ [1, n] and S ∈ [0, n(n+1)
],
2
time complexity of the above algorithm results to O(loop1 ) ∗ O(loop2 ) ∗ O(loop3 ) = O(n) ∗ O(n2 ) ∗ O(2n ∗
−3
3
n 2 ) = O(2n ∗ n 2 ). Space complexity for the above algorithm is the size of array storing smaller subsets,
SDG[n − 1][S]. This complexity is also exponential n ∗ S ∗ N o. of Subsets. Since S ∈ [0, n(n+1)
], the space
2
−3
3
2
n
n
2
2
complexity results to O(n) ∗ O(n ) ∗ O(2 ∗ n ) i.e. O(2 ∗ n ).
Algorithm 1 SDG: GeneratorUsingSumDistribution(n)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

SDG = {}
. Data structure to store the generated Subsets
for i ∈ {1, . . . , n} do
start sum = 0
mid sum = b i(i+1)
c
4
. end sum is equal to maxSum(i)
end sum = i(i+1)
2
universal set = {1, 2 . . . n}
. universal set is used to calculate the symmetric subsets
for j ∈ {start sum, . . . , mid sum} do
if (j == 0) then
SDG[i] = {φ}
end if
SDG[i][j] = SDG[i − 1][j]
for subset ∈ SDG[i − 1][j − i] do
subset.append(i)
SDG[i][j].append(subset)
. Adding ith element in every subset of SDG[i − 1][j − i]
end for
if j 6= (i − j) then
SDG[i][end sum − j] = universal set − SDG[i][j]
. Symmetric subsets.
end if
end for
F ree(SDG[i − 1])
end for
return SDG[n]

5.3

Subset Generation using Length-Sum Distribution

Along with Sum Distribution, we have established several concepts, theories and formulas for Length − Sum
Distribution as well. It counts the number of subsets of Xn of length l and sum S where Xn = {1, 2, 3 . . . n},
l ∈ [0, n] and S ∈ [0, n(n+1)
], represented by LD[n][S][l]. The recursive equation (Equation 2) establishes
2
the theory for the Length-Sum distribution.
In this section, we present the designed generator. Algorithm 2 is the pseudo-code for generating all the
subsets of Xn of length l and sum S. This distribution is recursive and uses LDG to store the previous
output which is initialized at Line 1 and Line 10. The notation for LDG is different than notation of LD.
We denote the count the number of subsets of Xn of length l and sum S where Xn = {1, 2, 3 . . . n}, l ∈ [0, n]
] by LD[n][S][l]. However, LDG[i][j][k] consists of all subsets of Xi with length = j and
and S ∈ [0, n(n+1)
2
Sum = k. In LDG notation for length and sum are reversed for easier calculations.
In Algorithm 2, extra values of LDG (LDG[i−1]) are freed in Line 26 to minimize the space consumption.
In Line 5, Line 9 and Line 13, we iterate through smaller natural numbers, length range and possible values
of sum respectively. Line 6 to Line 12 we define max sum for Xi , bases cases of LDG[i][j], start sum and
end sum. Line 13 to Line 24 iterates through feasible values of sum between start sum and end sum. The
desired set of subsets, LDG[i][j][k] consists of all subsets of LDG[i − 1][j][k] and LDG[i − 1][j − 1][k − i]. We
include ith element in every subset of LDG[i−1][j −1][k −i]. For each of these resulting subsets, a symmetric
subset of length (i − j) and sum (end sum − k) is calculated by subtracting the subset from universal set.
Line 15 to Line 23 essentially execute these steps and returns the final result at Line 28.
−3
The value of maximum number of subsets has exponential bound, O(2n ∗ n 2 ), as described in Appendix
−3
7. Therefore, the time complexity for (loop4 ) in Line 16 is O(2n ∗ n 2 ). Since, l ∈ [1, n] and S ∈ [0, n(n+1)
]
2
time complexity of the above algorithm results to O(loop1 ) ∗ O(loop2 ) ∗ O(loop3 ) ∗ O(loop4 ) i.e. O(n) ∗
−3
−3
5
O(n)∗O(n2 )∗O(2n ∗n 2 ) = O(n4 ∗2n ∗n 2 ) = O(2n n 2 ). Space complexity for the above algorithm is the size
of array storing smaller subsets, LDG[n − 1]. This complexity is also exponential n ∗ l ∗ S ∗ (N o. of Subsets).
−3
Since, l ∈ [1, n] and S ∈ [0, n(n+1)
] the space complexity results to O(n) ∗ O(n) ∗ O(n2 ) ∗ O(2n ∗ n 2 ) =
2
−3
5
O(n4 ) ∗ O(2n ∗ n 2 ) i.e. O(2n ∗ n 2 ).
5.4

Subset Generation using Basic Bucket Algorithm

In this section, we present a new method which generate all the subsets of Xn with a particular sum. This
is a greedy algorithm. The look-up table that has been used, has been explained in Section 7. It has been
extensively used with this algorithm.
The core idea behind this enumeration technique is to use the various distribution values that we have
calculated so far, to construct all the subsets of Xn which sum up to S.
Given: The first concept used for Basic Bucket Algorithm is Element Distribution. We start with the exact
occurrence of each element of Xn in subsets of precise sum, S. This information is denoted by ED[n][S][e].
The next concept used is the number of subsets, among power set of Xn , where summation of all elements
is S. SD[n][S] denotes such count. For this algorithm, we consider SD[n][S] as number of empty buckets.
Buckets are storage data structures which are used to stack all the appropriate elements that compute
the total sum S. We iterate through all elements in descending order. During each iteration, an element is
assigned to one of the buckets. This method is about adding the correct element to the corresponding subset.
Properties: Element distribution and below properties help us ensure the correct placement for every
element.
1. An element e is added to a bucket b only if the addition results to the uniqueness among all existing
elements of the bucket b. This property is followed to guarantee that the generated result is a subset and
it is not a bag. A subset belongs to power sets of Xn P (Xn ).
2. An element e is added to a bucket b only if the addition of the element results to uniqueness amongst
all the buckets. We follow this property to ensure the generation of correct number of subsets of sum S.
3. An element e is added to a bucket b only if on adding the new element, the sum of the bucket does not
the exceed the desired sum S. This property allows us to create subsets of sum S.
Unfortunately, we have no rule which forces only the generation of subsets with sum S. Many subsets
with sum less than S are generated during the first iteration of this technique. These subsets are called the

Algorithm 2 LDG: GeneratorUsingLengthSumDistribution(n)
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:

LDG = {}
LDG[0][0] = LD[1][0] = {}
. Base Cases
LD[1][1] = {[1]}
. Base Cases
universal set = [1, 2 . . . n]
. universal set is used to calculate the symmetric subsets
for i ∈ {2, . . . , n} do
max sum = i(i+1)
2
LDG[i][0] = {[1]}
LDG[i][max sum] = {universal set}
for j ∈ {1, . . . , 2i } do
. Iterarting till mid point
LDG[i][j] = {}
start sum = j(j+1)
2
end sum = i ∗ j − i(i−1)
2
for k ∈ {start sum, . . . , end sum} do
LDG[i][j][k] = LDG[i − 1][j][k]
if j ≥ 1 and k ≥ i and i ≤ k ≤ i(i+1)
then
2
for subset ∈ LDG[i][j − 1][k − i] do
subset.append(i)
LDG[i][j][k].append(subset) . Adding ith element in every subset of LDG[i − 1][j − 1][k − i]
end for
end if
if j 6= (i − j) then
LDG[i][i − j][end sum − k] = universal set − LDG[i][j][k]
. Symmetric subsets
end if
end for
end for
F ree(LDG[i − 1])
end for
Return LD[n]

undesired set. For every subset of the undesired set, A Sum(A) is less than S i.e. Sum(A) < S. Therefore,
we have converted this technique to a greedy algorithm. Instead of using this as a one time procedure, we
reapply it with modified values of element distribution, ED[n][S][e] and sum distribution, SD[n][S]. All
subsets are generated by applying the same technique on modified input in a greedy manner.
Uniqueness: The key step in successfully generating the full desired results is to maintain an efficient and
complete lookup table as described in Section 7. This lookup table which is maintained with the help of a
hash function and bit vectors, not only ensures uniqueness among and within the buckets but also makes
sure that all the undesired subsets of previous iterations are properly hashed. So, we do not re-generate the
same undesired set in the next iteration. We need to put extra effort to preserve the state of all undesired
sets from every iteration. The whole lookup table is no bigger than 2n and every subset: desired or undesired,
is stored in the form of one integer num, where num ∈ [0, 2n ]. With the aim of preserving the count of every
element from the set Xn , we maintain a log table for each round of iterations. The value of log table for
each element, at the start of every round is the summation of value of element distribution at the end of last
iteration of previous round and the count of all these elements from buckets which do not provide a subset
of desired sum.
Algorithm 3 calculates the element distribution before start of each round of Basic Bucket Algorithm.
Algorithm 4 initializes the buckets at the start of the algorithm. It finds the value of x and accordingly fill
the buckets with the starting elements. This method is called from Line 3 of the function GeneratingSubsets(n, S, SD[n][S], ED[n][S], prevW rongSubsets) from the main Algorithm 6. We find an appropriate
bucket for every element based on the properties of the Basic Bucket Algorithm. Functionality is defined
in Algorithm 5. While Algorithm 7 iterates though all the rounds of the bucket algorithm. All iterations of
every round is implemented by the Algorithm 6.

Algorithm 3 Basic BA: GetED(n, S, T able, wrongSubsets)
1: function GetED(n, S, T able, wrongSubsets)
2:
newT able = T able
3:
for subset ∈ wrongSubsets do
4:
for ele ∈ subset do
5:
newT able[ele]+ = 1
. Restoring all the ellments of wrongSubsets to the element distribution
6:
end for
7:
end for
8:
Return newT able
9: end function

Algorithm 4 Basic BA: InitializeBuckets(all buckets, T able, n, S , p)
1: function InitializeBuckets(all buckets, T able, n, S , p)
2:
q = count of non-zero entries of T able
3:
x = min(p, q)
4:
elements = x largest integers of Xn where T able[ele] 6= 0 ∀ ele ∈ elements
5:
Sort elements in descending order
6:
bucketIndex = 1
7:
for ele in elements do
8:
Add ele in all buckets[bucketIndex]
9:
bucketIndex + +
10:
end for
11: end function

For a given n and S, time complexity of the algorithm depends on the maximum number of subsets
and time to find a bucket for each element placement. Since, finding the bucket is an iterative algorithm,
time taken for this sub-method is also proportional to the number of subsets, SD[n][S]. Since, the value
−3
of maximum number of subsets has exponential bound, O(2n ∗ n 2 ), as described in Appendix 7, time

Algorithm 5 Basic BA: FindBucket(all buckets, ele, S)
1: function FindBucket(all buckets, ele, S)
2:
for bucket in all buckets do
3:
if any bucket entry is same as ele then
4:
Next
5:
else if on adding ele in bucket, Sum(bucket) > S then
6:
Next
7:
else if on adding ele in bucket, bucket becomes duplicate to any other bucket then
8:
Next
9:
else
10:
Return bucket
11:
end if
12:
end for
13:
Return F alse
14: end function

Algorithm 6 Basic BA: Generating Subsets(n, S, SD[n][S], ED[n][S], prevW rongSubsets)
Given: n, S, SD[n][S] and ED[n][S][i] where i ∈ [1, n]
desiredSubsets = [ ]
. desiredSubsets are all the subsets of Xn with sum S.
wrongSubsets = [ ]
. wrongSubsets are the set of undesired and smallersubsets.
T able = GetED(n, S, ED[n][S], prevW rongSubsets) . the count of every element in subsets of Xn with sum S
called from function GetED described in Algorithm 3
5: p = SD[n][S] : number of subsets of Xn with sum S

1:
2:
3:
4:

1: function GenerateSubsets
2:
all buckets = p empty buckets
. Initial Step
3:
initializeBuckets(all buckets, T able, n, S, p)
4:
f illBuckets = T rue
. Flag to control implementation of the while loop
5:
while (f illBuckets is set & (|all buckets| > 0)) do
6:
f ilBuckets = F alse
7:
q = count of non-zero entries of T able
8:
x = min(p, q)
9:
elements = x largest integers of Xn where T able[ele] 6= 0 ∀ ele ∈ elements
10:
Sort elements in descending order
11:
for ele ∈ elements do
12:
b = findBucket(all buckets, ele, S)
13:
if b is a bucket then
. When an elemnt can be inserted in a valid bucket.
14:
Add ele in bucket b
15:
f illBuckets = T rue
. If no element is alloted to any bucket in a full iteration.
16:
T able[ele] − −
17:
if Sum of the bucket b == S then
18:
desiredSubsets+ = b
19:
print bucket b
20:
Remove b from all buckets
21:
|all buckets| − −
22:
end if
23:
end if
24:
end for
25:
end while
26:
for bucket ∈ remaining buckets do
27:
wrongSubsets+ = bucket
28:
end for
29:
Return wrongSubsets, T able
30: end function

Algorithm 7 Basic BA: main Function(n, S)
1: function mainFunction(n, S)
2:
prevW rongSubsets = [ ]
3:
prevT able = ED[n][S]
4:
countSubsets = SD[n][S]
5:
while countSubsets > 0 do
6:
prevW rongSubsets, prevT able = GeneratingSubsets(n, S, countSubsets,
prevT able, prevW rongSubsets)
countSubsets = SD[n][S] = |prevW rongSubsets|
. Count of Subsets to be generated in next round is same as the size of wrong no. of subsets from previous
round.
8:
end while
9:
Return T rue
10: end function
7:

−3

−3

complexity is O(max(SD[n][S] · max(SD[n][S]) = O(2n ∗ n 2 · 2n ∗ n 2 ) = O(22n · n−3 ). Therefore, given
n and S, the time complexity to generate all the subsets is O(22n · n−3 ). Space complexity includes size of
two storages T able and all buckets, O(n) + O(2n ) = O(2n ).
5.5

Subset Generation using Frequency Driven Bucket Algorithms

After the basic bucket algorithm we present two more bucket algorithms. While the previous algorithm uses
the direct information provided by element distribution, ED[n][S][e] and sum distribution, SD[n][S], in
these two algorithms we use element distribution in decreasing or increasing order. In other words, instead
of assigning elements to a corresponding bucket in descending order, we assign elements to buckets based on
their frequencies. Frequency of an element in all the subsets of Xn with sum S, by definition, is equal to the
count of the elements, denoted by ED[n][S][e]. These algorithms are called Frequency-Driven (FD) Bucket
algorithms. These can be called minimum FD or maximum FD bucket algorithms.
Information used by these algorithms is same as the Basic Bucket Algorithm. While the basic bucket
algorithm is iterative, the minimum or maximum frequency driven algorithms are recursive. Information
required by this algorithm, properties of elements that should be followed and the measures by which we
ensure uniqueness (i.e. using log and lookup tables) is same as the primitive algorithm defined in Section
5.4.
Next, we generate all twenty subsets of X10 with Sum = 15. For both the algorithms, we select an
element based on minimum or maximum frequency. In case of Minimum FD bucket algorithm, we select
the maximum element with minimum frequency and recursively produce all the subsets of desired sum. For
Maximum FD, we select maximum element with maximum frequency. In Table 6, we log all the iterations
for generating all twenty subsets of X10 with Sum = 15. Following points briefly describe the working of
Minimum FD bucket algorithm:
1. By following the algorithm, we select element 10. Since, ED[10][15][10] = 3, first iteration generates 3
subsets: {{10, 5}, {10, 4, 1}, {10, 3, 2}}. This is shown in the first row of Table 7. All subsets are generated
in eight iterations.
2. In next three iterations, we choose elements-9, 8 and 7 respectively, to generate next thirteen subsets.
This will results in production of sixteen subsets.
3. In every iteration we update the count of elements according to the resulting subsets.
4. In fifth iteration, we select element 2 and recursively generate two subsets, {{2, 6, 4, 3}, {2, 5, 4, 3, 1}}.
For maximum frequency driven bucket algorithm we select the maximum element with maximum frequency in every iteration.
1. All twenty desired subsets are produced in seven iterations.
2. Since, ED[10][15][1] = ED[10][15][2] = 9 and max(1, 2), we select element 2 and generate nine subsets.
3. In second iteration we select element 4 and recursively generate next four subsets: {9, 6}, {9, 5, 1}, {9, 4, 2}
and {9, 3, 2, 1}.
4. Table 6 and Table 7 presents the log entries and subsets corresponding to all iterations of maximum FD
bucket algorithm for X10 with sum = 15.

Elements →
Iterations ↓
0th iteration
1st iteration
2nd iteration
3rd iteration
4th iteration
5th iteration
6th iteration
7th iteration

1 2 3 4 5 6 7 8 9 10
9
8
6
4
2
2
1
1

9
8
6
4
2
1
0
0

8
7
6
5
3
2
1
1

8
7
6
4
3
2
1
0

8
7
6
5
4
3
2
1

6
6
5
4
3
3
2
1

5
5
5
4
0
0
0
0

5
5
5
0
0
0
0
0

4
4
0
0
0
0
0
0

3
0
0
0
0
0
0
0

Elements →
Iterations ↓
0th iteration
1st iteration
2nd iteration
3rd iteration
4th iteration
5th iteration
6th iteration
7th iteration

1 2 3 4 5 6 7 8 9 10
9
5
3
0
0
0
0
0

9
0
0
0
0
0
0
0

8
4
2
1
1
1
1
0

8
4
0
0
0
0
0
0

8
5
4
2
1
1
1
0

6
4
3
1
1
0
0
0

5
3
2
2
2
2
1
0

5
2
2
1
1
1
0
0

4
2
2
1
1
0
0
0

3
2
1
1
0
0
0
0

Table 6: Log table for iterations of Minimum and Maximum Frequency Driven Bucket Algorithm. We are
generating all twenty subsets of X10 with Sum = 15. Every column denotes the frequency calculation for
ten elements and every row denotes the frequency calculations in every iteration. In this table the frequency
of every selected element in the previous iteration is marked as bold.

Iterations Selected Element
Subsets
|Subsets|
1st iteration
10
{{10, 5}, {10, 4, 1}, {10, 3, 2}}
3
2nd iteration
9
{{9, 6}, {9, 5, 1}, {9, 4, 2}, {9, 3, 2, 1}}
4
3rd iteration
8
{{8, 7}, {8, 6, 1}, {8, 5, 2}, {8, 3, 4}, {8, 4, 2, 1}}
5
4th iteration
7
{{7, 6, 2}, {7, 5, 3}, {7, 5, 2, 1}, {7, 4, 3, 1}}
4
5th iteration
2
{{2, 6, 4, 3}, {2, 5, 4, 3, 1}}
2
6th iteration
4
{{4, 6, 5}}
1
7th iteration
6
{{6, 5, 3, 1}}
1
T otal N umber of Subsets →
20
Iterations Selected Element
st

iteration

2

nd

iteration
iteration
iteration
iteration
iteration
iteration

4
1
10
9
8
7

1

2
3rd
4th
5th
6th
7th

Subsets
{{2, 1, 3, 4, 5}, {2, 1, 3, 9}, {2, 1, 4, 8}, {2, 1, 5, 7},
{2, 3, 4, 6}, {2, 3, 10}, {2, 4, 9}, {2, 5, 8}, {2, 6, 7}}
{{4, 1, 3, 7}, {4, 1, 10}, {4, 3, 8}, {4, 5, 6}}
{{1, 5, 9}, {1, 6, 8}, {1, 3, 5, 6}}
{{10, 5}}
{{9, 6}}
{{8, 7}}
{{7, 5, 3}}
T otal N umber of Subsets →

|Subsets|
9
4
3
1
1
1
1
20

Table 7: Log table for iterations of Minimum and Maximum Frequency Driven Bucket Algorithm. We are
generating all twenty subsets of X10 with Sum = 15. First column represent all the iterations, second
column shows the chosen element as per the frequency. Third column stores the subsets and the fourth
column denotes the count of these subsets.

5.6

Algorithm and Complexities

We state the pseudo codes for solving minimum and maximum FD bucket algorithms. Algorithm 8 updates the element distribution after every iteration and is called from Algorithm 10. This update ensures that correct number of subsets are generated. In Line 5, the element count is reduced according
to the answer generated so far. The main function which was defined in Algorithm 9, repeatedly calls the
GeneratingSubsetsbyF DBucketAlgo function and updates following information:
1.
2.
3.
4.

countSubsets - No. of subsets left.
f ullT able - Element distribution of Xn with Sum = S.
elements - Remaining elements which form remaining subsets.
elementsCovered - Elements which are not allowed or required to form remaining subsets.

Apart from these helper methods, the main functionality is presented in Algorithm 10. First we define
the input for our algorithm. Line 2 is the base case of our recursive algorithm. We terminate the recursion
when the desired sum S. S is less than zero or there are no elements left to generate the subsets. In Line
7 and Line 8 we find minKey and minV al pair. In case of Minimum FD algorithm (minKey, minV al)
is the largest element with minimum frequency, e ∈ [1, n] where ED[n][S][e] is minimum. For maximum
FD algorithm, we find (maxKey, maxV al), the largest element with maximum frequency. The pseudo code
for both algorithms are similar. Therefore, only minimum FD bucket algorithm is described. The main idea
behind this algorithm is to find minKey, and generate subsets of Xn with Sum = [S −minKey]. This means
by adding minKey to elementsCovered, in Line 10, we do not include it in future partial subsets. In Line
11, we recursively call GeneratingSubsetsbyF DBucketAlgo function with modified values. The remaining
part of the code is divided in two conditions which are based on the return values from Line 11. It can either
be empty or non-empty. minKey is appended to every returning subset of desiredSubsets[S − minKey] and
elementsCovered are updated accordingly. In last few lines, we increase the count of ED[n][S][e] for next
iteration. This step ensures that the correct subsets are created in next iteration too.
For a given n and S, time complexity of the maximum or minimum FD bucket algorithm depends on the
maximum number of subsets and time taken to solve one recursion. Since, iterating through all elements is a
recursive algorithm, time taken for this sub-method is also proportional to the number of subsets, SD[n][S].
−3
Since, the value of maximum number of subsets has exponential bound, O(2n ∗n 2 ), as described in Appendix
−3
−3
7, time complexity is O(max(SD[n][S] · max(SD[n][S]) = O(2n ∗ n 2 · 2n ∗ n 2 ) = O(22n · n−3 ). Therefore,
for given n and S,the time complexity to generate all the subsets is O(22n · n−3 ). Space complexity includes
size of two storages T able and desiredSubsets, O(n) + O(2n ) = O(2n ).

Algorithm 8 Max FD: GetED(n, S, T able, desiredSubsets)
1: function GetED(n, S, T able, desiredSubsets)
2:
newT able = T able
3:
for subset ∈ desiredSubsets do
4:
for ele ∈ subset do
5:
newT able[ele]− = 1
6:
end for
7:
end for
8:
Return newT able
9: end function

5.7

. Reducing count of elements according to desiredSubsets.

Subset Generation using Local Search

Our next enumeration technique for subset generation is called the Local Search. Before proceeding with
this algorithm, we define two new types of subsets called Maximal and Minimal subsets. They act as the
starting point for the local search algorithm.

Algorithm 9 Max FD: main Function(n, S)
1: function mainFunction(n, S)
2:
f ullT able = ED[n][S]
3:
countSubsets = SD[n][S]
4:
elements = [1, 2 . . . n]
5:
elementsCovered = [ ]
6:
while countSubsets > 0 do
7:
desiredSubsets = GeneratingSubsets(n, S, countSubsets,

. Available elements
. Elements covered so far

elements, elementsCovered, f ullT able)
countSubsets = SD[n][S] − |desiredSubsets|
Update f ullT able, elements, elementsCovered
. Reduce frequency of elements according to desiredSubsets.
10:
end while
11:
Return T rue
12: end function
8:
9:

Maximal and Minimal Subsets We present a new idea to categorize subsets of a given class. First,
we divide the power set of Xn , P (Xn ), on the basis of their sum and then further partition these subsets
according to their length. We have formulated and explained this selection process in Section 4.2.
For defining maximal subset we have the set of first n natural numbers, Xn , sum(S) which belongs to
[0, maxSum(n)] where maxSum(n) = n(n+1)
and length(l) which belongs to [0, n]. Consider, A denotes the
2
subsets of Xn with length l and sum S. We denotes A as A = {A1 , A2 . . . Ak } where k = LD[n][S][l], the
total count of subsets with length l and sum S. Ai represents ith subset of set A and Ai,j represents j th
element of subset Ai where j ∈ [1, l]. There exists a maximal subset of Xn of length l and sum S, Amaximal ,
is defined such that ∀j ∈ [1, l] Amaximal,j > Ap,j where p ∈ {[1, k] − maximal}. There also exists a minimal
subset, Aminimal , defined such that ∀j ∈ [1, l]Aminimal,j > Ap,j where p ∈ {[1, k] − minimal}.
The key point is that not all values of Amaximal,j will be greater than j th element of other subsets in
A but there will surely be a subset for which first q elements are greater than rest of the subsets, where
q ∈ [1, l]. In order to generate the subset Amaximal for Xn for a given sum S and length l, we find the smallest
possible element for every position, starting from the rightmost position. This pattern of element generation
will ensure largest possible elements at the start of the subset, resulting in the maximal subset. Similarly, we
find the largest possible element for every position of minimal subset starting from the rightmost position
which ensures the smallest possible element at the start of the subset, resulting in the desired minimal subset.
Table 8 displays the maximal and minimal subsets for every sum and length pair of X5 .
The core idea for the local search algorithm is to find all possible subsets of a particular length l and
sum S where our starting subset can be a maximal or minimal subset. We find subsets by iterating over
length between lmin and lmax where these are the minimum and maximum possible subsets of Xn with sum
s respectively. This is a heuristic algorithm. Next, we present a few examples to explain local search using
maximal and minimal subset respectively.
Maximal subset has the largest possible element at every position for a given sum S and length l.
Therefore, for local search starting with the maximal subset, we begin from left most element, decrement
the first permissible element followed by increment of next permissible element. On contrary, minimal subset
has smallest possible element at every position for a given sum S and length l. Therefore, we begin from left
most element, increment the first permissible element followed by decrement of next permissible element.
Every increment or decrement consists of one unit.
1. Figure 1 shows the local search example for n = 10, sum = 21 and length = 3 where the starting subset
is the maximal subset of respective length.
(a) We start with subset {6, 7, 8}. By decrementing the first permissible element 6 by 1 and incrementing
third permissible element 8 by 1, we generate the second subset {5, 7, 9}. We cannot increment the
second element of subset {6, 7, 8}, as on incrementing 7 by 1, we get 8 which creates duplication. In
this case, 7 is a non-permissible element.
(b) Next, we generate subsets :{{4, 8, 9}, {5, 6, 10}, {4, 7, 10}} from subset {5, 7, 9}.
(c) By following the same procedure, we generate all desired subsets of X10 with sum 21 and length 3
from a single maximal set Amaximal .

Algorithm 10 Max FD: GeneratingSubsetsbyFDBucketAlgo(n, S, SD[n][S], elements, elementsCovered, ED[n][S])
1: Given: n, S, SD[n][S] and ED[n][S][i] where i ∈ [1, n]
2: desiredSubsets = [ ]
. desiredSubsets are all the subsets of Xn with sum S.
3: f ullT able = GetED(n, S, ED[n][S], desiredSubsets) . the count of every element in subsets of Xn with sum S
called from function GetED described in Algorithm 8
4: p = SD[n][S] : number of subsets of Xn with sum S
1: function GenerateSubsets
2:
if S <= 0 or |elements| == 0 then
3:
Return desiredSubsets
4:
end if
5:
countSubsets = SD[n]
6:
while countSubsets > 0 do
7:
minV al = min(ED[n][S][e] > 0)
8:
minKey = max(e ∀e ∈ [1, n] & ED[n][S][e] == minV al)
9:
elements.remove(minKey)
10:
elementsCovered.add(minKey)
11:
desiredSubsets = GeneratingSubsets(n, S − minKey, countSubsets
, elements, elementsCovered, f ullT able)
12:
if desiredSubsets[S − minKey] is empty then
13:
countSubsets − −
14:
ED[n][S][minKey] − −
15:
desiredSubsets[S] = [[minKey]]
16:
print(desiredSubsets[S])
17:
elementsCovered.remove(minKey)
18:
else
19:
for A ∈ desiredSubsets[S − minKey] do
20:
ED[n][S][minKey] − −
21:
if (minKey ∈
/ A) & (minKey + sum(A) == S) then
22:
if A.append(minKey) is unique then
23:
countSubsets − −
24:
print(A)
25:
desiredSubsets[S].append(A)
26:
In elementsCovered add elements of A
27:
end if
28:
end if
29:
end for
30:
end if
31:
end while
32:
for e ∈ ED[n][S][e] <= 0 do
33:
elementsCovered.add(e)
34:
end for
35:
for A ∈ desiredSubsets & e ∈ A do
36:
ED[n][S][e] + +
37:
end for
38:
Return desiredSubsets
39: end function

Sum Length

Subsets

M aximalSubset M inimalSubset

0

0

φ

φ

φ

1

1

{{1}}

{1}

{1}

2

1

{{2}}

{2}

{2}

1

{{3}}

{3}

{3}

2

{{1, 2}}

{{1, 2}}

{{1, 2}}

1

{{4}}

{4}

{4}

2

{{1, 3}}

{{1, 3}}

{{1, 3}}

1

{{5}}

{5}

{5}

2

{{2, 3}, {1, 4}}

{2, 3}

{1, 4}}

2

{{2, 4}, {1, 5}}

{2, 4}

{1, 5}

3

{{1, 2, 3}}

{1, 2, 3}

{1, 2, 3}

2

{{3, 4}, {2, 5}}

{3, 4}

{2, 5}

3

{{1, 2, 4}}

{1, 2, 4}

{1, 2, 4}

2

{{3, 5}}

{3, 5}

{3, 5}

3

{{1, 3, 4}, {1, 2, 5}}

{1, 3, 4}

{1, 2, 5}

2

{{4, 5}}

{4, 5}

{4, 5}

3

{{2, 3, 4}, {1, 3, 5}}

{2, 3, 4}

{1, 3, 5}

3

{{2, 3, 5}, {1, 4, 5}}

{2, 3, 5}

{1, 4, 5}

4

{{1, 2, 3, 4}}

{1, 2, 3, 4}

{1, 2, 3, 4}

3

{{2, 4, 5}}

{2, 4, 5}

{2, 4, 5}

4

{{1, 2, 3, 5}}

{1, 2, 3, 5}

{1, 2, 3, 5}

3

{{3, 4, 5}}

{3, 4, 5}

{3, 4, 5}

4

{{1, 2, 4, 5}}

{1, 2, 4, 5}

{1, 2, 4, 5}

13

4

{{1, 3, 4, 5}}

{1, 3, 4, 5}

{1, 3, 4, 5}

14

4

{{2, 3, 4, 5}}

{2, 3, 4, 5}

{2, 3, 4, 5}

15

5

{{1, 2, 3, 4, 5}}

{1, 2, 3, 4, 5}

{1, 2, 3, 4, 5}

3

4

5

6

7

8

9

10

11

12

Table 8: Maximal and minimal subsets for every sum and length pair of X5 .

2. Figure 2 presents the local search example for n = 10, sum = 21 and length = 3 where the starting
subset is the minimal subset of respective length.
(a) We start with subset {2, 9, 10}. By incrementing the first permissible element 2 by 1 and decrementing
the second permissible element 9 by 1, we generate the second subset {3, 8, 10}. We can not decrement
the third element of subset {2, 9, 10}, as on decreasing 10 by 1, we get 9 which leads to duplication.
In this case, 10 is a non-permissible element.
(b) Next, we generate subsets :{{4, 7, 10}, {4, 8, 9}} from subset {3, 8, 10}.
(c) By following the same procedure, we generate all desired subsets of X10 with sum 21 and length 3
from a single minimal set, Aminimal .
3. While generating a subset using Local Search Algorithm, we ensure that the sum of subset is equal to the
desired target sum S, the subset do not contain duplicates and there is uniqueness among the subsets.
Uniqueness among and within these subset is ensured by using lookup technique introduced in Section
7. This establishes the correctness of the Local Search Algorithms using Maximal and Minimal Subsets.
4. Since we know the count of all subsets of Xn with Sum = S and Length = l, we generate all the subsets
and this approach is concluded only when all desired subset results are achieved. This establish the
completeness of the Local Search Algorithms using Maximal and Minimal Subsets.

Fig. 1: Local search for n = 10, sum = 21 and length = 3 with maximal subset as the starting point.

Fig. 2: Local search for n = 10, sum = 21 and length = 3 with minimal subset as the starting point.

Local Search using Maximal Subset: Algorithm 11 presents a procedure to generate all subsets of Xn
with particular sum S and length l where the seed subset is the maximal subset, Amaximal . We begin from
the left most element, decrement the first permissible element followed by increment of next permissible element. Each increment or decrement consists of one unit. In Algorithm 11, we use a queue data structure to

store all the resulting subsets, including maximal subset. We can iterate all the subsets in FCFS manner via
these method. We check the uniqueness among the subsets by using the concept of lookup table as defined
in Section 7. A subset is pushed in the queue only if its unique. This algorithm is terminated when all the
subsets are generated.
Local Search using Minimal Subset: Algorithm 12 represents a procedure to generate all subsets of
Xn with particular sum S and length l where the seed subset is the minimal subset, Aminimal . We begin
from left most element, increment the first permissible element followed by decrement of next permissible
element. Every increment or decrement consists of one unit. Algorithm 12 uses the same queue data structure
and checks the uniqueness among the subsets by using the concept of lookup table as Algorithm 11. This
algorithm is terminated when all subsets are generated.
Complexities: Time complexity of these algorithms is complexity of while loop × complexity of for loop,
i.e., maximum no. of subsets ∗ length of each subset. The complexity of the length of each subset variable is
O(n) but the time complexity of maximum no. of subsets variable is exponential. This makes the algorithm
−1
−3
2n
). The space complexity for these
exhaustive. Time complexity is O(2n · n 2 · n) = O(2n · n 2 ) = O( √
n
algorithms is equal to the size of storage queue i.e. maximum no. of subsets ∗ length of each subset. The
time complexity is similar. The complexity of the Length of each subset variable is O(n) but the space
2n
complexity of maximum no. of subsets variable is exponential, O( √
).
n

Algorithm 11 LS MaxS: Local Search for Maximal Subset
1: function localSearch(n, s, l)
2:
maximalSet =maximalSubset(n, s, l)
3:
queue.push(maximalSet)
4:
allSubsetsGenerated = LD[n][s][l]
5:
while allSubsetsGenerated > 0 do
6:
reqSet = queue.pop()
7:
for i = 1; i ≤ len − 1; i + + do
8:
if reqSet[i] − 1 > reqSet[i − 1] then
9:
reqSet[i]− = 1
. First decrementing the element by 1
10:
decrement = T rue
11:
end if
12:
for j = i + 1; j ≤ l; j + + do
13:
if reqSet[j] + 1 < reqSet[j + 1] then
14:
reqSet[j]+ = 1
15:
increment = T rue
16:
end if
17:
if (reqSet is unique) and (decrement) and (increment) then
18:
print reqSet
19:
queue.push(reqSet)
20:
allSubsetsGenerated − −
21:
end if
22:
end for
23:
end for
24:
end while
25: end function

6

Experimental Results

This section presents the experiments that we have conducted to validate the efficiency and effectiveness of
all the proposed algorithms.

Algorithm 12 LS MinS: Local Search for Minimal Subset
1: function localSearch(n, s, l)
2:
minimalSet =minimalSubset(n, s, l)
3:
queue.push(minimalSet)
4:
allSubsetsGenerated = LD[n][l][s]
5:
while allSubsetsGenerated > 0 do
6:
reqSet = queue.pop()
7:
for i = 1; i ≤ len − 1; i + + do
8:
if reqSet[i] + 1 < reqSet[i + 1] then
9:
reqSet[i]+ = 1
. First incrementing the element by 1
10:
increment = T rue
11:
end if
12:
for j = i + 1; j ≤ l; j + + do
13:
if reqSet[j] − 1 > reqSet[j − 1] then
14:
reqSet[j]− = 1
15:
deccrement = T rue
16:
end if
17:
if (reqSet is unique) and (decrement) and (increment) then
18:
print reqSet
19:
queue.push(reqSet)
20:
allSubsetsGenerated − −
21:
end if
22:
end for
23:
end for
24:
end while
25: end function

6.1

Summary of Alternate Enumeration Techniques

Following table summarizes all the alternate enumeration techniques to solve SSP.
Problem Statement: Find all subsets of P (Xn ) which sum up to S, where Xn is the set of first
n natural numbers, Xn = {1, 2 . . . n}
Algorithm
Core Idea
Time Complex- Space Complexity
ity
Backtracking Al- It is an improved and systematic brute force ap- O(n × 2n )
O(n)
gorithm (Naive) proach for generating various subsets with Sum =
(section-5.1)
S. We iterate through all 2n solutions in an orderly
fashion.
3
3
Subset Genera- This algorithm is a recursive generator based on O(2n ∗ n 2 )
O(2n ∗ n 2 )
tor using Sum the concept of Sum Distribution and uses subsets
Distribution
of X(n−1) to produce results for Xn .
(SDG)
Subsets of Xn with Sum = S are generated by
(section-5.2)
subsets of Xn−1 with Sum = (S − n).
5
5
Subset
Gen- This algorithm is a recursive generator based on O(2n ∗ n 2 )
O(2n ∗ n 2 )
erator
using the concept of Length-Sum Distribution and uses
Length-Sum
subsets of X(n−1) to produce results for Xn .
Distribution
Subsets of Xn with (Sum = S, Length = l) are
(LDG)
generated by subsets of Xn−1 with (Sum = S −
(section-5.3)
n, Length = l − 1).

Basic Bucket Al- The basic idea behind this enumeration technique
gorithm
is to use the various distribution values. We con(Basic BA)
sider SD[n][S] number of empty buckets, storage
(section-5.4)
data structures, and iterate through all elements
in descending order. During each iteration an element is assigned to one of the buckets. This method
is about adding the correct element to the corresponding subset. This is an iterative algorithm.
Maximum Fre- Information used by this recursive algorithm is
quency
Driven same as the basic bucket algorithm. Instead of
Bucket
Algo- choosing elements in descending order, we select
rithm
maximum element with maximum frequency to
(Max FD)
generate all SD[n][S] number of subsets of Xn with
(section-5.5)
Sum = S.
Minimum
Fre- This algorithm is contrary to maximum FD bucket
quency
Driven algorithm. Information used by this is also similar
Bucket
Algo- to the basic bucket algorithm. We select maximum
rithm
element with minimum frequency to generate all
(Min FD)
SD[n][S] number of subsets of Xn with Sum = S.
(section-5.5)
Local
Search This heuristic algorithm finds all desired subsets
using Maximal by choosing the maximal subset as the seed. MaxiSubset
mal subset has the largest possible element at every
(LS MaxS)
position for a given sum(S) and length(l). There(section-5.7)
fore, we begin from left most element, decrement
the first permissible element followed by increment
of next permissible element. Every increment or
decrement consists of one unit.
Local Search us- This heuristic algorithm also finds all desired subing Minimal Sub- sets by choosing the minimal subset as the seed
set
(starting point). Minimal subset has smallest pos(LS MinS)
sible element at every position for a given sum(S)
(section-5.7)
and length(l). Therefore, we begin from left most
element, increment the first permissible element followed by decremental of next permissible element.
Every increment or decrement consists of one unit.

O(22n · n−3 )

O(2n )

O(22n · n−3 )

O(2n )

O(22n · n−3 )

O(2n )

n

2
O( √
)
n

n

2
)
O( √
n

2
O( √
)
n

2
)
O( √
n

n

n

Table 9: Summary of the core concepts and ideas of all the alternate enumeration techniques to solve subset
sum problem. First column introduces every algorithm, second column presents the core idea behind the
algorithm and the last two columns states their time and space complexities.
6.2

Experimental Setup

We have carried out various sets of experiments on an i7-2600 machine with 64GB of RAM to compare and
analyze the performance of our algorithms under various considerations. We define the experimental setup
and measuring parameters before comparing the performances.
Due to symmetric property of SSP, we choose random sum values in lower part of the sum range i.e.
S ≤ midSum(n). In Figure 3, we show different plots for number of subsets of Xn for various sums.
These figures help us estimate the problem space for generating results of alternate enumeration techniques.
We select the value of S as 2n to show the behavior of number of subsets of Xn with sum S when S
has the complexity O(n). Similarly, we choose the value of S as midSum(n) − n because the number of
subsets of Xn with this sum are
q in order of O(midSum(n)). This upper bound of the Sum Distribution
SD[n][midSum(n)] = S(n) ≈

6
π

· 2n · n

−3
2

is explained in Appendix 7. Table 10 presents the count of

number of subsets Xn with S = 2n and S = ( n(n+1)
− n). This table gives an estimate of the values
4

plotted in Figure 3. Figure 3(a, c) plot the number of subsets of Xn with (n ∈ [1, 250], S = 2n) and
(n ∈ [1, 50], S = ( n(n+1)
− n)) respectively. Figure 3(b, d) plot the log to the base 10 of number of subsets
4
of Xn with (n ∈ [1, 250], S = 2n) and (n ∈ [1, 50], S = ( n(n+1)
− n)) respectively. Since the values of number
4
of subsets for a particular S increases exponentially with n, we have plotted Figure 3(b, d) by using the
logarithmic function. This helps in approximating the size of the problem space.

n

Count of Subsets
of Xn with
S = 2n

n

Count of Subsets
of Xn with
S = ( n(n+1)
− n)
4

6

2

6

2

7

5

7

5

8

8

8

8

9

13

9

13

10

134

10

24

50

416868

15

521

100

482240364

20

11812

150

114613846376

30

7206286

200

11954655830925

40

5076120114

250

732839540340934

50

3831141038816

Table 10: Count of number of subsets Xn with S = 2n and S = ( n(n+1)
− n) respectively.
4

6.3

Excess Subset Generation Analysis

Given Xn and a sum S, we know how many subsets of Xn have sum S. This value is SD[n][S]. For each
algorithm, in order to generate these SD[n][S] subsets we may explore few extra subsets of Xn whose sum
not equal to S.
In naive backtracking method, at every step of subset generation we either include or exclude an element.
This creates a recursive tree and a branch is terminated when the current sum exceeds the target. This
way we explore more subsets than desired sum. Similarly, in rest of the alternate enumeration techniques in
order to generate all subsets of Xn with sum S, we explore more subsets than desired number of subsets.
In this analysis we measure this extra exploration. In Table 11 we present the ratios of subsets explored to
total number of subsets of Xn with sum S i.e. SD[n][S]. The first three columns of this table states (n, S)
pair and the value of SD[n][S] for all these pairs. The remaining eight columns denote the ratio of explored
subsets to the number of subsets in the final solution for all eight alternate enumeration techniques. With
every ratio we also represent the time taken by the algorithm to generate the solution set. For every value
of n and S, we bold the least ratio and least time taken by an algorithm.
Following observations can be made based on the data presented in Table 11:
1. For a given value of n and S, desired ratio is a fraction of the number of subsets to be generated to the
total number of subsets of Xn with Sum S i.e. SD[n][S]. For example, n = 12 and S = 24, the number
of subsets of X12 with Sum = 24 are 67. Therefore, the value of SD[12][24] = 67.
2. Every column corresponding to a given algorithm presents the ratio of number of subsets explored to
generate the desired subsets to the total number of subsets of Xn with sum S. For example for naive
algorithm, given n = 12 and S = 24, the number of subsets explored for generating all subsets of X12
with Sum = 24 are 737. Therefore, the desired ratio for these values is: 737
67 = 11.
3. The ratio for all algorithms should be greater than the desired ratio. If not, then it implies that complete
result has not been generated. In this table for a given n and S, the ratio for all algorithms is greater

(a) Plot of number of subset of Xn at S = 2n vs n

(b) Plot of log10 (number of subset of Xn ) at 2n vs n

(c) Plot of number of subset of Xn at S = ( n(n+1)
− n) vs(d)
n Plot of log10 (number of subset of Xn ) at S = ( n(n+1)
− n) vs n
4
4

Fig. 3: Plot of number of subsets of Xn against sums in smaller and larger ranges. For smaller range we select
S = 2n and plot graph for n varying from 1 to 250. (a) Figure represents graph for number of subsets of Xn
with S = 2n where n ∈ [1, 250]. (b) Figure represents graph for number of subsets of Xn with S = 2n with
logarithmic base 10 where n ∈ [1, 250]. For larger range we select S = ( n(n+1)
− n) and plot graph for n
4
varying from 1 to 50. (c) Figure represents graph for number of subsets of Xn with S = ( n(n+1)
− n) where
4
n(n+1)
n ∈ [1, 50]. (d) Figure represents graph for number of subsets of Xn with S = ( 4 − n) with logarithmic
base 10 where n ∈ [1, 50].

4.

5.

6.

7.
8.

n

than the desired ratio. This observation and the correctness of these algorithms ensure the completeness
of the results.
Naive algorithm explores most number of subsets in order to generate the desired subsets. Naive is the
worst performing enumeration technique compares to all our proposed algorithms. This shows that all
our alternate enumeration techniques perform better than the benchmark algorithm.
Ratios of LS MaxS and LS MinS are closer to the desired ratio for a given n and S.
(a) Since LS MaxS and LSMinS are heuristic algorithms, they explore lesser number of subsets as
compared to naive algorithm.
(b) For example, given n = 12 and S = 24, the number of subsets explored for LS MaxS and LS MinS
103
are 93 and 103 respectively creating a ratio of 93
67 = 1.3881 and 67 = 1.5373.
(c) The drawback for these algorithm is that they do not generate results for higher values of n and S
within short amount of time. This is explained more in Section 6.4.
After Local Search algorithms, LDG and SDG are next in good performance ranking. Ratio for LDG is
smaller and closer to desired ratio than SDG.
(a) Since LDG is a simple dynamic algorithm which generate the subsets based on their sum and length,
it goes to one more level of categorization among subsets and minimizes the excess exploration of
undesired subsets.
(b) Given n = 12 and S = 24, the number of subsets explored by LDG are 150 and ratio is 150
67 = 2.2388.
(c) LDG has precedence over others as it can enumerate all subsets of Xn for a considerable values of n
within short amount of time. The numbers are shown in Table 18 of Section 6.4.
(d) SDG explores more subsets than LDG but it performs better than naive. While naive implementation
involves a recursive tree based on the inclusion and exclusion of an element at every step, SDG builds
the subset by using the exact formula defined in Section 4.
(e) Given n = 12 and S = 24, the number of subsets explored by SDG are 214 and ratio is 214
67 = 3.1940.
Performance of Max FD and Min FD is similar to SDG. For n = 12 and S = 24, MaxFD explores 166
subsets and Min FD explores 241 subsets. For other pairs of n and S these values are very close.
Basic Bucket algorithm (Basic BA) also performs better than naive but can not compute all subsets for
a considerable value of n and S within short amount of time.
S

|Subsets|

12 24

67

12 27

84

15 30

186

15 45

521

16 32

253

17 59

1764

20 40

860

20 85

11812

22 104 41552

Naive
11
(0.00247)
20.5952
(0.00178)
21.4194
(0.00795)
23.3282
(0.01184)
60.6087
(0.01118)
27.0947
0.03996)
73.6390
(0.03277)
28.4236
(0.30453)
34.7394
(1.21103)

SDG
3.1940
(0.009596)
2.7857
(0.012512)
6.2097
(0.014521)
2.8177
(0.056801)
8.2806
(0.017711)
2.9127
(0.233748)
30.0447
(0.055301)
2.9261
(2.08991)
2.9706
(8.53939)

LDG
2.2388
(0.00103)
2.0952
(0.00116)
1.6882
(0.00499)
1.3013
(0.00472)
1.6719
(0.00615)
1.3622
(0.01556)
1.8189
(0.04656)
1.6258
(0.1357)
1.8080
(0.52493)

Basic BA
5.0896
(1.618)
5.1548
(2.394)
4.7742
(21.208)
5.4664
(77.48)
-

Max FD
2.4776
(0.195)
2.6190
(0.405)
2.3871
(1.381)
2.8503
(14.031)
2.3478
(2.341)
2.9892
(153.31)
2.2667
(21.923)
(6981.574)
-

Min FD
3.5970
(1.822)
4.2262
(2.958)
4
(7.641)
1.3129
(353.746)
3.7470
(11.761)
-

LS MaxS
1.3881
(0.019)
1.3690
(0.02)
1.1882
(0.11)
1.0211
(0.798)
1.1621
(0.211)
1.0176
(10.144)
1.0707
(2.81)
1.2332
(572.839)
-

LS MinS
1.5373
(0.016)
1.2976
(0.024)
1.2903
(0.133)
1.0058
(0.955)
1.2332
(0.255)
1.1037
(12.058)
1.1191
(3.438)
1.2281
(664.875)
-

Table 11: The ratios of subsets explored to total number of subsets of Xn with sum S i.e. SD[n][S] is
presented in this table. The first three columns of this table states (n, S) pair and the value of SD[n][S] for
all these pairs. The remaining eight columns denote subsets explored ratio for all eight alternate enumeration
techniques. With every ratio we also represent the time taken by the algorithm to generate the solution set.
The least ratio and least time taken for every n and S are presented in bold.

6.4

Comparative Analysis of Enumeration Algorithms

In this section, we present the time taken by various enumeration techniques under different conditions.
Experiments defined in this section are categorized based on the range of input sum value corresponding
to the set of natural numbers Xn . Given Xn , Sum(A) belonging to the range [0, maxSum(n)] = [0, n(n+1)
]
2
where A ∈ P (Xn ). Choosing different values of sum between 0 to maxSum(n) is the core idea behind these
experiments. Table 12 summarizes the explanation of all these experiments.
Experiments / Compara- Description and Examples
tive Analysis
CA-SSR [1, 2n]
For this experiment we randomly choose sum S1 from a
smaller range and calculate the
time taken to generate subsets of
Xn with Sum = S1 . For every
values of n, this smaller range
varies from 1 to 2n i.e. ∀n, S1 ∈
[1, 2n].
CA-LSR [midSum(n) − For this experiment we rann, midSum(n)]
domly choose sum S2 from a
larger range and calculate the
time taken by all the algorithms
to generate subsets of Xn with
Sum = S2 . For every values of
n, this larger range varies from
midSum(n) − n to midSum(n)
i.e. ∀n S2 ∈ [midSum(n) −
n, midSum(n)].
CA-FSV
In this experiment instead of
choosing random vales of S for
every algorithm against every
n, we fix few pairs of (n, S1 )
and (n, S2 ) for all the algorithms
where S1 = 2 ∗ n and S2 =
midSum(n) − n
CA-SLN
For this experiment instead of
fixing the value of sum S, we
vary S from 0 to maxSum(n) =
n(n+1)
. This experiment helps
2
us in analyzing the performance
of SDG and LDG algorithms
against Naive (backtracking) algorithm. In this experiment we
enumerate all 2n subsets of Xn

Algorithms Tables or Figures
Basic BA,
Max FD,
Min FD,
LS MaxS,
LS MinS

Table 13: Time taken (in seconds) by Basic BA, Max FD and
Min FD in CA-SSR.
Table 14: Time taken (in seconds) by LS MaxS and LS MinS
in CA-SSR.

Basic BA,
Max FD,
Min FD,
LS MaxS,
LS MinS

Table 15: Time taken (in seconds) by Basic BA, Max FD and
Min FD in CA-LSR.
Table 16: Time taken (in seconds) by LS MaxS and LS MinS
in CA-LSR.

Basic BA,
Max FD,
Min FD,
LS MaxS,
LS MinS,
LDG,
SDG
SDG,
LDG,
Naive

Table 17: presents the time taken
by Max FD, Min FD, Basic BA,
LS MaxS, LS MinS, LDG and
SDG algorithms where S1 = 2∗n
and S2 = midSum(n) − n

Table 18: presents the comparison of SDG and LDG with naive
backtracking algorithm. This table presents the time taken(in
sec) while enumerating all 2n
subsets of Xn for every value of
sum S in range [0, n(n+1)
]. This
2
is the time taken by these algorithms to enumerate each and
every subset.
Figure 4: Plot of SDG, LDG and
Naive algorithm while enumerating all 2n subsets of Xn for
every value of sum S in range
].
[0, n(n+1)
2

Table 12: Summary of the experimental setup for Comparative Analysis of Enumeration Algorithms. First
column states the name, second columns describes the experiment, third column lists the algorithms for
which the experiment is carried out and the fourth column presents the tables and figures stating the time
taken by different algorithms under several conditions.

We have drawn these tables and shown these times for demonstrative purposes. We have observed the
following by running all the eight algorithms:
1. From comparative analysis of algorithms in smaller range (CA-SSR) we can see that Basic BA, Max FD,
Min FD, LS MaxS and LS MinS generate subsets till n equal to 22, 36, 36, 44 and 44 respectively and
takes less than 35, 000 seconds.
– Since LS MaxS and LS MinS explores lesser number of extra subsets as shown in Section 6.3, it takes
lesser amount of time than bucket algorithms.
– Among these five algorithms, Basic BA explores maximum number of subsets, takes most time for
execution and can generate results till smaller values of n.
2. Comparative analysis of algorithms in larger range (CA-LSR) follows similar pattern as CA-SSR. The
value of sum selected in this range has higher value of SD[n][S] which results in more execution time.
LS MaxS and LS MinS perform the best in this experiment.
3. Comparative Analysis with Fixed Sum Values (CA-FSV) allows us to compare seven algorithms: Max
FD, Min FD, Basic BA, LS MaxS, LS MinS, LDG and SDG for a fixed value of n and S.
– From this comparative study, we can see that LDG and SDG outperforms all the other algorithms.
They can be executed till n = 36 and takes least amount of time.
– Even though SDG and LDG explores more number of subsets, additional information required by
these algorithms is much lesser than the additional information required by Local Search and Bucket
Algorithms.
– SDG and LDG does not require the values of SD[n][S] and ED[n][S][e] at every step of execution.
They do not need to maintain the current state of algorithm. This reduces the execution time.
4. From comparative analysis of SDG, LDG and Naive (CA-SLN) we compare LDG, SDG with naive to
show that our alternate enumeration techniques performs better than the existing algorithms. Using
nave algorithm, we are not able to generate all the subset above n equal to or greater than 24. This
limits the execution. But LDG and SDG can easily be computed till n = 34 in less than 40 minutes.
These timings are implementation and machine dependent. The above results show that even though some
algorithms explore fewer extra subsets but they take more time due to lack of efficient implementation,
storage and memory constraint.

Time taken(in sec) by LS MaxS in CA-SSR
n S Time(in sec) n S
Time(in sec)

Time taken(in sec) by LS MinS in
n S Time(in sec) n S Time(in sec)

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1
1
1
3
4
10
5
16
20
11
6
1
17
4
32
17
33
10
28
14
21

0.00015
0.00012
0.00015
0.00024
0.00023
0.00098
0.00039
0.0037
0.0094
0.0018
0.00070
0.00060
0.01081
0.00086
0.30375
0.00682
0.46984
0.00144
0.19325
0.00403
0.03176

24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

47
36
10
17
5
8
8
53
58
31
56
50
47
62
74
56
58
32
55
46
44

19.862
2.0454
0.0023
0.0114
0.002251
0.002551
0.00289
168.747
510.344
1.00335
411.957
124.164
67.4379
1748.339
18096.70
588.9686
951.2177
1.890367
561.6479
76.02470
48.61702

1
1
1
2
7
6
9
4
22
9
10
3
15
26
20
11
28
10
31
28
20

0.00020
0.00019
0.00020
0.00022
0.00073
0.00049
0.00092
0.00047
0.01392
0.00122
0.00145
0.00069
0.00634
0.09706
0.02005
0.00148
0.15588
0.00149
0.43241
0.22006
0.02313

24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

47
19
52
22
10
47
58
10
12
10
27
43
44
32
34
59
13
55
26
14
40

21.2260
0.01893
77.8854
0.05621
0.00278
41.2712
434.903
0.00344
0.00514
0.00396
0.356276
26.97922
36.25960
1.74147
3.16681
1143.04
0.00915
556.808
0.35234
0.01238
18.9293

Table 13: Time taken (in seconds) by Local Search using Maximal Subset (LS MaxS) and Local Search using
Minimal Subset (LS MinS) in CA-SSR where S1 is randomly chosen and ∀n, S1 ∈ [1, 2n].

n S

n S
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1
1
2
3
5
2
2
16
13
13
9
16
26
31
34
6
19
36
15
41

Time taken(in
sec)
by Basic BA
in CA-SSR
0.000551
0.0004.20
0.000138
0.000247
0.000405
0.000849
0.000885
0.05103
0.01842
0.02192
0.00265
0.08399
7.03249
60.6872
241.571
0.00106
0.75584
1261.39
0.09077
12918.6

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

1
1
1
3
6
10
12
7
20
24
24
5
2
9
11
7
3
33
11
37
29
42
22
4
5
29
27
13
15
17
57
47
36
71

Time taken(in
sec)
by Max FD
in CA-SSR
0.00076
0.000564
0.000569
0.001332
0.003052
0.000837
0.00139
0.00384
0.12669
0.19757
0.220844
0.0011010
0.0003778
0.0040118
0.007174
0.0024759
0.0008509
4.143428
0.007366
11.79708
1.868481
42.95121
0.274363
0.0009
0.001708
2.35588
1.51263
0.029837
0.068043
0.113950
1822.731
237.329
21.1548
32840.56

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

1
1
2
4
1
1
3
3
7
24
21
10
23
22
34
15
20
15
9
6
34
42
9
29
33
13
51
24
33
41
43
23
14
70

Time taken(in
sec)
by Min FD
in CA-SSR
0.00094
0.00065
0.00072
0.00156
0.00073
0.00073
0.00016
0.00172
0.00503
0.29195
0.14098
0.00586
0.25498
0.21270
4.35665
0.04607
0.15957
0.03706
0.00526
0.00236
8.08626
52.7242
0.00573
2.61190
8.01348
0.03223
523.152
0.73111
9.51999
71.6738
117.805
0.71141
0.08665
33113.13

Table 14: Time taken (in seconds) by Basic Bucket Algorithm (Basic BA), Maximum Frequency Driven
Bucket Algorithm (Max FD) and Minimum Frequency Driven Bucket Algorithm (Min FD) in CA-SSR
where S1 is randomly chosen and ∀n, S1 ∈ [1, 2n].

n S

n S
4
5
6
7
8
9
10
11
12
13
14
15

3
6
4
12
17
18
25
31
35
40
48
50

Time taken(in
sec)
by Basic BA
in CA-LSR
0.00079
0.00102
0.00044
0.00882
0.02263
0.11157
0.32170
1.59752
9.34307
39.5506
437.383
1846.33

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3
5
7
10
14
18
22
27
33
39
45
52
60
68
76
85
95
105

Time taken(in
sec)
by Max FD
in CA-LSR
0.00143
0.00153
0.00252
0.00522
0.01324
0.02944
0.07514
0.15790
0.41121
1.38157
4.16112
12.2192
39.9648
132.079
434.065
1426.70
4850.73
17189.86

n S
3
4
5
6
7
8
9
10
11
12
13
14
15

2
4
3
6
7
10
13
21
31
37
33
46
57

Time taken(in
sec)
by Min FD
in Exp-2
0.00081
0.00129
0.00117
0.00329
0.00451
0.01452
0.03446
0.20658
1.87448
12.5400
7.19542
166.192
793.294

Table 15: Time taken (in seconds) by Basic Bucket Algorithm (Basic BA), Maximum Frequency Driven
Bucket Algorithm (Max FD) and Minimum Frequency Driven Bucket Algorithm (Min FD) in CA-LSR
where S2 is randomly chosen and ∀n, S2 ∈ [midSum(n) − n, midSum(n)].

Time taken(in sec) by LS MaxS in CA-LSR
n S Time(in sec) n S
Time(in sec)

Time taken(in sec) by LS MinS in CA-LSR
n S Time(in sec) n S
Time(in sec)

3
4
5
6
7
8
9
10
11
12

3
4
5
6
7
8
9
10
11
12

1
2
5
6
8
18
20
18
23
30

0.00003
0.00025
0.00057
0.00049
0.00067
0.001429
0.003262
0.00491
0.01419
0.04604

13
14
15
16
17
18
19
20
21
22

39
49
47
54
72
67
87
97
94
114

0.12096
0.34326
0.77065
2.65762
10.4998
30.6323
149.328
649.048
1635.28
8633.37

1
2
6
7
11
13
14
23
29
31

0.00062
0.00374
0.00473
0.01077
0.00115
0.0102
0.00251
0.00898
0.02194
0.05642

13
14
15
16
17
18
19
20
21
22

41
50
56
56
66
68
92
100
114
116

0.12125
0.33774
0.87691
2.99347
11.1003
32.6975
124.407
639.238
1881.25
8897.909

Table 16: Time taken (in seconds) by Local Search using Maximal Subset (LS MaxS) and Local Search
using Minimal Subset (LS MinS) in CA-LSR where S2 is randomly chosen and ∀n, S2 ∈ [midSum(n) −
n, midSum(n)].

|Subsets| Max FD

n

S

12
12
14
14
15
15
16
16
17
17
18
18
20
20
21
21
22
22
25
25
27
27
30
30

24
67
27
84
28
134
38
274
30
186
45
521
32
253
52
965
34
343
59
1764
36
461
67
3301
40
806
85
11812
42
1055
94
21985
44
1369
104 41552
50
2896
137 283837
54
4649
162 1038222
60
9141
202 7206286

0.195
0.405
0.808
3.9
1.381
14.031
2.341
45.83
4.414
153.31
7.913
541.046
21.923
6981.574
38.779
25300.63
64.492
295.741
831.93
-

Min FD Basic
BA
1.822
1.618
2.958
2.394
3.95
14.76
54.175 161.639
7.641
21.208
353.746 1388.5
11.761 77.48
1224.328
27.817 236.119
52.816 649.679
146.823
268.505
842.423
-

LS
LS MinS LDG
SDG
MaxS
0.019
0.016
0.00103 0.009596
0.02
0.024
0.00116 0.012512
0.066
0.065
0.00289 0.013285
0.215
0.256
0.00315 0.03134
0.11
0.133
0.00499 0.014521
0.798
0.955
0.00472 0.056801
0.211
0.255
0.00615 0.017711
2.882
3.394
0.0103 0.11678
0.412
0.501
0.00821 0.024524
10.144 12.058 0.01556 0.233748
0.791
0.96
0.02192 0.034023
39.129 45.385 0.03646 0.473109
2.81
3.438
0.04656 0.055301
572.839 664.875 0.1357 2.08991
5.177
6.298
0.0664 0.072871
2084.648 2421.476 0.22368 4.134605
9.411
11.516 0.09218 0.095904
0.52493 8.53939
52.604 64.216 0.57455 0.211722
2.35755 73.2227
155.258 190.273 1.06806 0.352428
10.77463 345.7571
733.963 897.121 1.921185 98.64595 -

Table 17: The values of CA-FSV. We fix few pairs of (n, S1 ) and (n, S2 ) for Max FD, Min FD, Basic BA, LS
MaxS, LS MinS, LDG and SDG algorithms where S1 = 2 ∗ n and S2 = midSum(n) − n. This table shows
time taken (in seconds) by all alternate techniques for calculating for these pairs.

n
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

|Subsets|
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152

LDG
0.00030
0.00024
0.00032
0.00037
0.00053
0.00061
0.00099
0.00122
0.00218
0.00257
0.00391
0.00532
0.00863
0.01223
0.02119
0.03060
0.05147
0.07002
0.12088
0.21260

SDG
0.00018
0.00013
0.00015
0.00017
0.00023
0.00027
0.00032
0.00039
0.00052
0.00072
0.00103
0.00174
0.00272
0.00483
0.00927
0.01531
0.02669
0.05230
0.10512
0.20231

Naive
0.0008
0.0012
0.0014
0.0026
0.0054
0.0116
0.0218
0.0423
0.0854
0.2137
0.4542
0.8522
1.5655
3.5153
6.1746
12.9676
24.3167
44.9257
92.8140
170.9037

22
23
24
25
26
27
28
29
30
31
32
33
34

4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
2147483648
4294967296
8589934592
17179869184

0.44724
0.77863
1.64562
3.01883
6.22996
11.55410
23.83728
46.01338
97.38387
184.78691
375.63728
755.37561
2130.2298

0.39577
0.81253
1.60156
3.13995
6.21826
12.60573
25.29129
49.41213
98.06444
202.59311
407.96308
844.82139
2363.4442

364.9816
689.0156
-

Table 18: Comparison of SDG and LDG with naive backtracking algorithm. This table presents the time
]. This is
taken(in sec) while enumerating all 2n subsets of Xn for every value of sum S in range [0, n(n+1)
2
the time taken by these algorithms to enumerate each and every subset in CA-SLN.

Fig. 4: Plot of SDG, LDG and Naive algorithm while enumerating all 2n subsets of Xn for every value of
sum S in range [0, n(n+1)
]. This graph plots time taken by these algorithms to enumerate each and every
2
subset in CA-SLN.

7

Conclusion

Subset Sum Problem, also referred as SSP, is a well-known important problem in computing, cryptography
and complexity theory. We extended the traditional SSP and suggested various alternate enumeration techniques. Instead of finding one subset with target sum, we find all possible solution of SSP. Therefore, for
X = {5, 4, 9, 11} and S = 9, the solution to our version of SSP is both {5, 4} and {9}. We confined our
problem domain by considering first n natural numbers as set Xn . In other words, we enumerate all (2n − 1)
power set of a set.
We have analyzed the distribution of P (Xn ) over sum, length and count of individual elements. We
introduced four types of distributions: Sum Distribution, Length Distribution, Length-Sum Distribution and
Element Distribution. We extended the concept by explaining their formulae and algorithms, along with
illustrations, which showed a definite pattern and relations among these subsets. These distributions are
prepossessing procedures for various alternate enumeration techniques for solving SSP.
We developed Backtracking Algorithm (Naive) algorithm. It is an improved and systematic brute force
approach for generating various subsets with Sum = S. Instead of searching exhaustively elements are
selected systematically. We iterate through all 2n solutions in this an orderly fashion. The inputs for this
algorithm are the set of first n natural numbers Xn and Sum = S. Time and space complexities for this
algorithm are O(n × 2n ) and O(n) respectively.
We have proposed Subset Generator using Sum Distribution(SDG). This algorithm is a recursive generator based on the concept of Sum Distribution and uses subsets of X(n−1) to produce results for Xn . This
algorithm uses the formula defined in Equation 1. This algorithm is executed using dynamic programming.
Subsets of Xn with Sum = S are generated by subsets of Xn−1 with Sum = S and Sum = (S − n). Time
3
3
and space complexities for this algorithm are O(2n ∗ n 2 ) and O(2n ∗ n 2 ) respectively.
We have proposed Subset Generator using Length-Sum Distribution (LDG). This algorithm is a recursive
generator based on the concept of Length-Sum Distribution and uses subsets of X(n−1) to produce results
for Xn . This algorithm uses the formula defined in Equation 2. This algorithm is executed using dynamic
programming. Subsets of Xn with (Sum = S, Length = l) are generated by subsets of Xn−1 with (Sum =
S, Length = l) and (Sum = S − n, Length = l − 1). Time and space complexities for this algorithm are
5
5
O(2n ∗ n 2 ) and O(2n ∗ n 2 ) respectively.
We have also proposed Basic Bucket Algorithm (Basic BA). The basic idea behind this enumeration
technique is to use the various distribution values. We consider SD[n][S] number of empty buckets, storage
data structures, and iterate through all elements in descending order. It uses the value of Element Distribution
for generating all the desired subsets. During each iteration an element is assigned to one of the buckets.
This method is about adding the correct element to the corresponding subset. This is a greedy algorithm.
This method uses the concept of lookup table explained in Section 7 and ensures uniqueness among and
within the subsets. Time and space complexities for this algorithm are O(22n · n−3 ) and O(2n ) respectively.
Next, we have extended the concept of Basic Bucket Algorithm (Basic BA) to propose two new bucket
algorithms: Maximum Frequency Driven Bucket Algorithm (Max FD) and Minimum Frequency Driven
Bucket Algorithm (Min FD). Information used by these recursive algorithms are same as the basic bucket
algorithm. For Max FD, instead of choosing elements in descending order, we select maximum element with
maximum frequency to generate all SD[n][S] number of subsets of Xn with Sum = S. For Min FD we
select maximum element with minimum frequency to generate all SD[n][S] number of subsets of Xn with
Sum = S. These methods use the concept of lookup table explained in Section 7 and ensure uniqueness
among and within the subsets. Time and space complexities for this algorithm are O(22n · n−3 ) and O(2n )
respectively.
We have proposed two more algorithms Local Search using Maximal Subset (LS MaxS) and Local Search
using Minimal Subset (LS MinS). Maximal and Minimal Subsets are a new idea for categorizing subsets
of a given class. First, we divide the power set of Xn , P (Xn ), on the basis of their sum and then further
partition these subsets according to their length. LS MaxS is a heuristic algorithm. It finds all the desired
subsets by choosing the maximal subset as the seed. Maximal subset has largest possible element at every
position for a given sum(S) and length(l). Therefore, we begin from left most element, decrement the first
permissible element followed by increment of next permissible element. LS MinS is also a heuristic algorithm
also finds all desired subsets by choosing the minimal subset as the seed. Minimal subset has the smallest
possible element at every position for a given sum(S) and length(l). Therefore, we begin from left most
element, increment the first permissible element followed by decremental of next permissible element. Every

n

2
) and
increment or decrement consists of one unit. Time and space complexities for this algorithm are O( √
n
n

2
) respectively.
O( √
n

Conjecture There are algorithms that can enumerate all solutions of Subset Sum Problem for set Xn and
sum S where 0 ≤ S ≤ n(n+1)
with O(SD[n][S]) complexity.
2
An optimal algorithm should enumerate exactly SD[n][S] subsets which are part of the solution.
This work can be extended in following ways:
1. By amortizing and combining different set of sums as one input set. Instead of running one sum at a
time, we can group the sum values for running various alternate enumeration techniques. This will save
the execution time by avoiding recalculations of subsets for smaller ranges.
2. Additionally, we can reduce the execution time of alternate enumeration techniques. These techniques
are implementation and machine dependent. These timings are also data structure dependent. As part
of future work, we would like to explore more data structures and more powerful machines to reduce the
running times furthermore.
3. We have seen that the Local Search algorithm using Maximal or Minimal Subset comparatively explores
less number of extra subsets and have better execution time than bucket algorithms. We can enhance
this algorithm by using element distribution to limit the heuristic search, by finding different starting
points and applying better distance formula for traversing through the solution space.

Acknowledgement
We thank Kannan Srinathan and Geeta Hooda for their discussion on this work.

Appendix
Lookup Technique
Mapping of each subset with a unique integer is the basic concept used to define a lookup table for power
sets of Xn , where Xn = {1, 2 . . . n}. Lookup table ensures uniqueness among the subsets and within elements
for a subset. This table helps us to maintain the uniqueness at runtime of any algorithm. This technique is
implemented with the help of bit vectors. Bit vector is a compact data structure
which hashes each subset
Pl
A = {A1 , A2 . . . Al } to the corresponding integer, denoted by num, Snum = i=1 2Ai −1 . We consider a hash
of size 2n . This hash will maintain a one-to-one mapping between all the subsets of Xn and is denoted by
P (Xn ).
Upper Bound on Sum Distribution
In this section, we use definitions and formulas presented in 3. By using the maximum limit on the number
of subsets with a particular sum, we find an upper bound of our problem.
SD[n], defined in Section 4.1 represents the count of all the subsets of Xn divided over sum S where
(Table 1). The maximum value of SD[n] is found at midSum(n) = b n(n+1)
c. Table
S ∈ [1, b] and b = n(n+1)
2
4
19 represents the value of SD[n][midSum(n)] for first 15 natural numbers.

n

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

sd[n][midSum(n)] 1 1 2 2 3 5 8 14 23 40 70 124 221 397 722

Table 19: Values of SD[n][midSum(n)] for first 15 natural numbers

For each n, value of SD[n][midSum(n)] presented in table 19 is the coefficient of x

n(n+1)
4

q in the expansion
−3
of {(1 + x)(1 + x )(1 + x ) . . . (1 + x )}. This coefficient is denoted as S(n) and S(n) ≈ π6 · 2n · n 2 [16].
Therefore, value of maximum number of subsets with sum as midSum(n) has exponential bound, O(2n ·
−3
n 2 ). This result is vastly used throughout the thesis in order to find complexities of various enumeration
techniques.
2

3

n

References
1. Austrin, P., Kaski, P., Koivisto, M., Määttä, J.: Space–time tradeoffs for subset sum: An improved worst case
algorithm. In: International Colloquium on Automata, Languages, and Programming. pp. 45–56. Springer (2013)
2. Austrin, P., Kaski, P., Koivisto, M., Nederlof, J.: Subset sum in the absence of concentration. In: LIPIcs-Leibniz
International Proceedings in Informatics. vol. 30. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)
3. Beier, R., Vöcking, B.: Random knapsack in expected polynomial time. In: Proceedings of the thirty-fifth annual
ACM symposium on Theory of computing. pp. 232–241. ACM (2003)
4. Fomin, F.V., Kratsch, D.: Exact exponential algorithms. texts in theoretical computer science. an eatcs series
(2010)
5. Galil, Z., Margalit, O.: An almost linear-time algorithm for the dense subset-sum problem. SIAM Journal on
Computing 20(6), 1157–1189 (1991)
6. Gilmore, P., Gomory, R.E.: Multistage cutting stock problems of two and more dimensions. Operations research
13(1), 94–120 (1965)
7. Gilmore, P., Gomory, R.: The theory and computation of knapsack functions. Operations Research 14(6), 1045–
1074 (1966)
8. Hardy, G.H., Wright, E.M.: An introduction to the theory of numbers. Oxford University Press (1979)
9. Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. Journal of the ACM
(JACM) 21(2), 277–292 (1974)
10. Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. Journal
of the ACM (JACM) 22(4), 463–468 (1975)
11. Koiliaris, K., Xu, C.: A faster pseudopolynomial time algorithm for subset sum. arXiv preprint arXiv:1507.02318
(2015)
12. Lokshtanov, D., Nederlof, J.: Saving space by algebraization. In: Proceedings of the forty-second ACM symposium
on Theory of computing. pp. 321–330. ACM (2010)
13. Pisinger, D.: Linear time algorithms for knapsack problems with bounded weights. Journal of Algorithms 33(1),
1–14 (1999)
14. Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Mathematical programming 66(1-3), 181–199 (1994)
15. Schnorr, C.P., Euchner, M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Mathematical programming 66(1-3), 181–199 (1994)
16. Sullivan, B.D.: On a conjecture of andrica and tomescu. Journal of Integer Sequences 16(2), 3 (2013)
17. T. Cormen, C. Leiserson, R.R., Stein., C.: Introduction to algorithms. (2014), the MIT Press, 3rd edition
18. Valluri, S.R., Karlapalem, K.: Subset queries in relational databases. arXiv preprint cs/0406029 (2004)
19. Wikipedia: Subset sum problem — wikipedia, the free encyclopedia (2016), https://en.wikipedia.org/w/
index.php?title=Subset_sum_problem&oldid=736749803, [Online; accessed 29-August-2016]
20. Woeginger, G.J.: Exact algorithms for np-hard problems: A survey. In: Combinatorial OptimizationEureka, You
Shrink!, pp. 185–207. Springer (2003)

