Sum of Subsets – How to solve using backtracking

Sum of Subsets Problem: Given a set of positive integers, find the combination of numbers that sum to given value M.

Sum of subsets problem is analogous to the knapsack problem. The Knapsack Problem tries to fill the knapsack using a given set of items to maximize the profit. Items are selected in such a way that the total weight in the knapsack does not exceed the capacity of the knapsack. The inequality condition in the knapsack problem is replaced by equality in the sum of subsets problem. Given the set of n positive integers, W = {w1, w2, …, wn}, and given a positive integer M, the sum of the subset problem can be formulated as follows (where wi and M correspond to item weights and knapsack capacity in the knapsack problem):

\[ sum_{i=1}^{n} w_i x_i = M \]

Where, \[ x_i in { 0, 1 } \]

Numbers are sorted in ascending order, such that w₁ < w₂ < w₃ < …. < w_n. The solution is often represented using the solution vector X. If the ith item is included, set xi to 1 else set it to 0. In each iteration, one item is tested. If the inclusion of an item does not violet the constraint of the problem, add it. Otherwise, backtrack, remove the previously added item, and continue the same procedure for all remaining items. The solution is easily described by the state space tree. Each left edge denotes the inclusion of wi and the right edge denotes the exclusion of w_i. Any path from the root to the leaf forms a subset. A state-space tree for n = 3 is demonstrated in Fig. (a).

Algorithm for Sum of subsets

The algorithm for solving the sum of subsets problem using recursion is stated below:

Algorithm

 SUB_SET_PROBLEM(i, sum, W, remSum)
// Description : Solve sub of subset problem using backtracking
// Input : 	
W: Number for which subset is to be computed
i: Item index
sum : Sum of integers selected so far
remSum : Size of remaining problem i.e. (W – sum)

// Output : Solution tuple X

if

 FEASIBLE_SUB_SET(i) == 1 

then

if

(sum == W) 

then

    print X[1…i]
  

end

else

  X[i + 1] ← 1		
  SUB_SET_PROBLEM(i + 1, sum + w[i] + 1, W, remSum – w[i] + 1 )
  X[i + 1] ← 0	// Exclude the ith item
  SUB_SET_PROBLEM(i + 1, sum, W, remSum – w[i] + 1 )

end

function

FEASIBLE_SUB_SET(i)
  

if

(sum + remSum ≥ W) AND (sum == W) or (sum + w[i] + 1 ≤ W) 

then

return

0
  

end

return

1

The first recursive call represents the case when the current item is selected, and hence the problem size is reduced by w[i].

The second recursive call represents the case when we do not select the current item.

Complexity Analysis

It is intuitive to derive the complexity of sum of the subset problem. In the state-space tree, at level i, the tree has 2i nodes. So, given n items, the total number of nodes in the tree would be 1 + 2 + 2² + 2³ + .. 2ⁿ.

T(n)    =   1 + 2 + 2² + 2³ + .. 2ⁿ = 2ⁿ⁺¹ – 1 = O(2ⁿ)

Thus, sum of sub set problem runs in exponential order.

Examples

Problem: Consider the sum-of-subset problem, n = 4, Sum = 13, and w₁ = 3, w₂ = 4, w₃ = 5 and w₄ = 6. Find a solution to the problem using backtracking. Show the state-space tree leading to the solution. Also, number the nodes in the tree in the order of recursion calls.

Solution:

The correct combination to get the sum of M = 13 for given W = {3, 4, 5, 6} is [3, 4, 6]. The solution vector for [3, 4, 6] would be X = [1, 1, 0, 1] because element 5 is not chosen, so X[3] = 0. Let’s derive the solution using backtracking. The numbers in W are already sorted.

Set X    =   [0, 0, 0, 0]

Set Sum = 0. Sum indicates summation of selected numbers from W.

Step 1 :     i = 1, Adding item w_i

Sum = Sum + w_i = Sum + w₁ = 0 + 3 = 3

Sum ≤ M, so add item i to solution set.

X[i] = X[1] = 1 ⇒ X =[1, 0, 0, 0]

Step 2 :     i = 2, Adding item w₂

Sum = Sum + w_i = Sum + w₂ = 3 + 4 = 7

Sum ≤ M, so add item i to solution set.

X[i] = X[2] = 1 ⇒ X =[1, 1, 0, 0]

Step 3 :     i = 3, Adding item w₃

Sum = Sum + w_i = Sum + w₃ = 7 + 5 = 12

Sum ≤ M, so add item i to solution set.

X[i] = X[3] = 1 ⇒ X =[1, 1, 1, 0]

Step 4 :     i = 4, Adding item w₄

Sum = Sum + w_i = Sum + w₄ = 12 + 6 = 18

Sum > M, so backtrack and remove the previously added item from the solution set.

X[i] = X[3] = 0 ⇒ X =[1, 1, 0, 0].

Update Sum accordingly. So, Sum = Sum – w₃ = 12 – 5 = 7

And don’t increment i.

Step 5 :     i = 4, Adding item w₄

Sum = Sum + w_i = Sum + w₄ = 7 + 6 = 13

Sum = M, so solution is found and add item i to solution set.

X[i] = X[4] = 1 ⇒ X =[1, 1, 0, 1] A complete state space tree for given data is shown in Fig. (b)

At level i, the left branch corresponds to the inclusion of number w_i and the right branch corresponds to exclusion of number w_i. The recursive call number for the node is stated below the node. Node 8 is the solution node. The bold solid line shows the path to the output node.

Example:

Analyze sum of subsets algorithm on data :

M = 35 and

i)      w = {5, 7, 10, 12, 15, 18, 20}

ii)     w = {20, 18, 15, 12, 10, 7, 5}

iii)    w = {15, 7, 20, 5, 18, 10, 12} Are there any discernible differences in the computing time ?

Solution:

Let us run the algorithm on first instance w = {5, 7, 10, 12, 15, 18, 20}.

Items in sub set	Condition	Comment
{ }	0	Initial condition
{ 5 }	5 < 35	Select 5 and Add next element
{ 5, 7 }	12 < 35	Select 7 and Add next element
{ 5, 7, 10 }	22 < 35	Select 20 and Add next element
{ 5, 7, 10, 12 }	34 < 35	Select 12 and Add next element
{ 5, 7, 10, 12, 15 }	49 > 35	Sum exceeds M, so backtrack and remove 12
{ 5, 7, 10, 15 }	37 > 35	Sum exceeds M, so backtrack and remove 15
{ 5, 7, 12 }	24 < 35	Add next element
{ 5, 7, 12, 15 }	39 > 35	Sub set sum exceeds, so backtrack
{ 5, 10 }	15 < 35	Add next element
{ 5, 10, 12 }	27 < 35	Sub set sum exceeds, so backtrack
{ 5, 10, 12, 15 }	42 > 35	Sub set sum exceeds, so backtrack
{ 5, 10, 15 }	30 < 35	Add next element
{ 5, 10, 15, 18 }	48 > 35	Sub set sum exceeds, so backtrack
{ 5, 10, 18 }	33 < 35	Add next element
{ 5, 10, 18, 20 }	53 > 35	Sub set sum exceeds, so backtrack
{ 5, 10, 20 }	35	Solution Found

There may be multiple solutions. A state-space tree for the above sequence is shown here: The number in the leftmost column shows the element under consideration. The left and right branches in the tree indicate inclusion and exclusion of the corresponding element at that level, respectively.

Numbers in the leftmost column indicate elements under consideration at that level. A gray circle indicates the node that cannot accommodate any of the next values, so we will cut sort them from further expansion. White leaves do not lead to a solution. An intermediate white node may or may not lead to a solution. The black circle is the solution state.

We get the four solutions:

• {5, 10, 20}
• {5, 12, 18}
• {7, 10, 18}
• {15, 20}

For efficient execution of the subset sum problems, input elements should be sorted in non-decreasing order. If elements are not in non-decreasing order, the algorithm does more backtracking. So second and third sequences would take more time for execution and may not find as many solutions as we get in the first sequence.

Example:

Solve the sum of subset problems using backtracking algorithmic strategy for the following data: n = 4 W =(w₁, w₂, w₃, w₄) = (11, 13, 24, 7) and M = 31.

Solution:

Items in sub set	Condition	Comment
{ }	0	Initial condition
{ 11 }	11 < 31	Add next element
{ 11, 13 }	24 < 31	Add next element
{ 11, 13, 24 }	48 < 31	Sub set sum exceeds, so backtrack
{ 11, 13, 7 }	31	Solution Found

State-space tree for a given problem is shown here:

In the above graph, the black circle shows the correct result. The gray node shows where the algorithm backtracks. Numbers in the leftmost column indicate elements under consideration at that level. The left and right branches represent the inclusion and exclusion of that element, respectively.

We get two solutions:

• {11, 13, 7}
• {24, 7}

Popular problems solved using backtracking:

Backtracking is useful in solving the following problems:

• N-Queen problem
• Sum of subset problem
• Graph coloring problem
• Knapsack problem
• Hamiltonian cycle problem

---

Additional Reading: Read More