Sum of subsets problem by backtracking 

We are given n distinct positive numbers (weights)
The objective is to find all combination of weights whose sum is equal to given weights m
State space tree is generated for all the possibilities of the subsets
Generate the tree by keeping weight <= m

1. Sum of Subsets Problem
By
Backtracking
Presentationby
HasanainALshadoodee
Backtracking

2. Learning Outcomes
At the end of session viewers will be to
Apply backtracking approach to solve sum of subsets problem
Presentation by_Hasanain ALshadoodee
2

3. Presentationby_HasanainALshadoodee
3
Introduction
We are given n distinct positive numbers (weights)
The objective is to find all combination of weights whose
sum is equal to given weights m
State space tree is generated for all the possibilities of
the subsets
Generate the tree by keeping weight <= m

4. Example
Considertheexamplegivenbelow
n=4
W{1:4}={5,10,15,20}
m=25
Findthesumofsubsetequaltom
Presentationby_HasanainALshadoodee
4

5. Examplen=4
W{1:4}={5,10,15,20}
m=25
Presentationby_HasanainALshadoodee
5
0,50
5,45
15,35
30,20 15,20
35, 0 15, 0
5,35
5,20
25, 0
X1=1
X2=1
X3=1
X2=0
X3=0
X4=1 X4=0
X3=0
X4=1
Solution
X1,x2,x3,x4={1,0,0,1}
First node two value one the
value is the subset=0
And second value
Summation of all value
=5+10+15+20
=50
0+5=5 50-5=45
45-10=35
5+10=15

6. Think and Write
Presentationby_HasanainALshadoodee
6
Findanothersubsetwhichisequaltomwhere
n=4
W{1:4}={5,10,15,20}
m=25
0,50
0,45
10,35
25,20
25, 0
Solution
X1,x2,x3,x4={0,1,1,0}
X1=0
X2=1
X3=1
X4=0
Without increase 50-5=45
45-10=350+10=10

7. subset sum problem using
backtracking python Code Answer
Presentationby_HasanainALshadoodee
7

8. Another Example
Presentationby_HasanainALshadoodee
8
theproblemistofindasubsetofagivenset
S={S1,S2,……,Sn}ofnpositiveintegerswhosesumis
equaltoagivenpositiveinteger“d“.
S1<=S2<=…….<=Sn

9. Presentationby_HasanainALshadoodee
9
Ex..ForS={1,3,4,5}2d=8
SLo={1,3,4}=8 SLo={3,5}=8
0
1
4
8 4
1
5 1
0
3
7 3
0
4 0
6 1 8
StateSpaceTree
X=3
X=1
X=4
X=5
3

10. Presentationby_HasanainALshadoodee
10