Scribd
Upload
463 views11 pages

27 Sum of Subsets Using Backtracking

The document discusses the Sum of Subsets problem, which involves finding all subsets of distinct positive numbers that sum to a given value m. It outlines the problem's constraints, provides examples using variable and fixed-sized tuples, and describes the algorithm for solving the problem through backtracking. Additionally, it includes a sample question related to the problem for further understanding.

Uploaded by

Prudhvi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
463 views11 pages

27 Sum of Subsets Using Backtracking

The document discusses the Sum of Subsets problem, which involves finding all subsets of distinct positive numbers that sum to a given value m. It outlines the problem's constraints, provides examples using variable and fixed-sized tuples, and describes the algorithm for solving the problem through backtracking. Additionally, it includes a sample question related to the problem for further understanding.

Uploaded by

Prudhvi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 11

DESIGN AND ANALYSIS OF ALGORITHMS

Session -27

SUM OF SUBSETS PROBLEM BY BACKTRACKING

1
SUM OF SUBSETS
Problem Definition: Given n distinct positive numbers wi,
and m, find all subsets whose sums are m.
• Explicit Constraints :
• Xi = { j / j is an integer and 1 <= j <= n }
• Implicit Constraints :
1. No two xi’s are same
2. Sum of the chosen weights must be equal to m.
3. To avoid generation of multiple instances of the same
subsets)

We can formulate this problem using Fixed tuple or


Variable tuples.
VARIABLE- SIZED TUPLE
Ex:- n=4, ( w1, w2, w3, w4 )= ( 11,13, 24, 7 ), m=31.

• Solutions are ( 11, 13, 7 ) and ( 24, 7 )

• Rather than representing the solution by wi ’s, we can


represent by giving the indices of these wi
• Now the solutions are ( 1, 2, 4 ) and ( 3, 4 ).

• Different solutions may have different-sized tuples.


• We use the following condition to avoid generating
multiple instances of the same subset ( e.g., ( 1,2,4)
and (1,4,2) )
xi < xi+1
Subset Tree for n=4 (variable- sized tuple )
1

x1=1 x1=4
x1=2
x1=3
3 4 5
2

x2=4 x2=3 x2=4 x2=4


x1=2
x2=3
1 1
8 9
6 7 0 1
x3=3 x3=4 x3=4 x3=4
1 1 1 9
2 3 4
x4=3
1
6
Nodes are numbered as in Breadth first search.
FIXED- SIZED TUPLE
• In this method, each solution subset is
represented by an n-tuple (x1,x2,…..x n).
• x i = 0 if wi is not chosen and xi = 1 if wi is chosen

Ex:- n=4, ( w1, w2, w3, w4 )= ( 11,13, 24, 7 ), m=31.

• Solutions are ( 11, 13, 7 ) and ( 24, 7 )


• Solutions are:
• X=(1,1,0,1) and X=(0,0,1,1)

6
SUBSET TREE FOR N = 4 ( FIXED – SIZED TUPLE )

x1=1 x1= 0

x2=1 x2= 0 x2=1 x2= 0

x3=1 x3 = 0

x4=1 x4=0

1110 1011 0111 0001


BOUNDARY CONDITIONS OF SUM OF SUBSETS
Algorithm SumOfSub( s, k, r )

// Find all subsets of w[ 1:n ] that sum to m

// It is assumed that w[1] ≤ m and ∑ wi ≥ m

x[ k ]=1; // left child

if( s + w[k] = m ) then write( x[ 1: k ] ) ; // Subset found

else if ( s + s [ k ] + s[ k+1 ] ≤ m )

then SumOfSub( s+ w[k], k+1, r- w[k] )

// Generate right child and evaluate Bk

if ( ( s + r – w[ k ] ≥ m ) and ( s + w[ k+1 ] ≤ m ) ) then

x[ k ] = 0;

} SumOfSub( s, k+1, r- w[k] ) ;

}
EX:- N=6, M=30, W [ 1:6 ]= { 5,10,12,13,15,18 }
PORTION OF STATE SPACE TREE GENERATED BY SUMOFSUB.
CIRCULAR NODES INDICATE SUBSETS WITH SUMS EQUAL TO M.
• Example 7.6 (Figure 7.10)
• n=6, w[1:6]={5,10,12,13,15,18}, m=30
SAMPLE QUESTIONS

• What is the Sum of Subsets problem


• Describe the problem statement of the Sum of Subsets. What
are the inputs and outputs of the problem
• Explain about state space tree in sum of subsets problem
• Solve sum of subsets by using
Input: set[] = {4, 16, 5, 23, 12}, sum = 9

11

You might also like