SUBSET SUM

What is a Set?
 What is a Set?
Collection of distinct elements
 What is a Set?
Collection of distinct elements
(Order does not matter)
(No duplicate elements allowed)
What is a Subset?
 What is a Subset?
A set formed by including some or all or
no elements from another set
How is a Subset formed ?

Let’s take an Example Set

 How is a Subset formed ?

Set: {3, 34, 4, 12, 5, 2}

 How is a Subset formed ?

Set: {3, 34, 4, 12, 5, 2}

To form a subset, each element has a choice:

To be included
Or not to be included
 How is a Subset formed ?

Set: {3, 34, 4, 12, 5, 2}

2x2x2x2x2x2
These choices are
independent for
each element
 How is a Subset formed ?

Set: {3, 34, 4, 12, 5, 2}

2x2x2x2x2x2

So if a set has n elements:

Total subsets = 2ⁿ
Instead of solving the whole problem at once,
We break it down into smaller decisions

Each decision creates a smaller version of

the same problem
Solve these smaller problems
Then combine their results
Instead of solving the whole problem at once,
We break it down into smaller decisions

Each decision creates a smaller version of

the same problem
Solve these smaller problems
Then combine their results
Instead of solving the whole problem at once,
We break it down into smaller decisions

Each decision creates a smaller version of

the same problem
Solve these smaller problems
Then combine their results

This is the general principal of,

Recursion ,
Backtracking,
Dynamic Programming
Lets look at the Problem statement
Given a set S = {a₁, a₂, …, aₙ} and an integer T,
(T = Target weight)
Find all subsets S' ⊆ S such that:
Sum of elements in S′ = T
Example
Set: {2, 3, 5, 6, 8}
Target: 8
Output:
Set: {2, 3, 5, 6, 8}
Target: 8
Output:
{2, 6}, {3, 5}, {8}
But finding Subsets for an array is
difficult
Instead we breakdown the problem
and find Subsets for a Single Element
Finding Subset for a single
element is Easy
 Finding Subset for a single
element is Easy
For a single elemnt ‘a’
 Finding Subset for a single
element is Easy

{a}
For a single elemnt ‘a’
 Finding Subset for a single
element is Easy

{a}
For a single elemnt ‘a’

{a} {}
 {a}
Included Not Included

{a} {}
 {a}
Included Not Included

{a} {}
2 Possible Subsets for
an Element
So at every level of Recursion
we solve for a Single Element
To build Subsets for an array
[1, 2, 3]
 []

We take an Empty Set

 []
[1] []
And make a Choice for the first element ‘1’
Either Included or Excluded
 []
[1] []

[1,2] [1]

Now we make Choice for the

next Element ‘2’
 []
[1] []

[1,2] [1] [2] []

 []
[1] []

[1,2] [1] [2] []

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

At last for Element ‘3'
 []
[1] []

[1,2] [1] [2] []

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

 []
[1] []

[1,2] [1] [2] []

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

 [] All possible Subsets
[1] []

[1,2] [1] [2] []

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

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

 [] If given Target is ‘3'
[1] [] then :

[1,2] [1] [2] []

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

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

Only 2 Subsets’ Sum result to the given Target

 [] i=0

[1] [] i=1

[1,2] [1] [2] [] i=2

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] [] i=3

 [] i=2

3] [] i=3
i=3
 i=3
Stop as soon as i = n (Size of given Array)
Lets look at the Algorithim
 Required functions and Parameters

printSubsets ( arr[] , n , i , ans[], size )

arr[] → Original input array (the set of elements we choose from)

n → Total number of elements (used to stop recursion when i == n)
i → Current index (decides which element we are currently processing)
ans[] → Temporary array storing the current subset being built
size → Number of elements in the current subset (used for tracking and printing)
Printing all the Subsets
Printing all the Subsets

Algorithm to Include an Element

ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
Printing all the Subsets

Algorithm to Include an Element

Including an Element from Main Array to

temporary ans[] Array
ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);

Calling the Function Again (RECURSION)

Printing all the Subsets

ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
 ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
Printing all the Subsets
 ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
Printing all the Subsets

Algorithm to Exclude an Element

printSubsets( arr, n, i + 1, ans, size );

 ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
Printing all the Subsets

Algorithm to Exclude an Element

No change in the
size of ans[] Array

printSubsets( arr, n, i + 1, ans, size );

 ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
Printing all the Subsets

printSubsets( arr, n, i + 1, ans, size );

 ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
Printing all the Subsets
printSubsets( arr, n, i + 1, ans, size );
 ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
Printing all the Subsets
printSubsets( arr, n, i + 1, ans, size );

Condition for Base case (i = n)

if (i == n)
{
for (int j = 0; j < size; j++)
cout << ans[j] << " " << endl;
return;
}
 ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
Printing all the Subsets
printSubsets( arr, n, i + 1, ans, size );

Condition for Base case (i = n) []

if (i == n) [1] []
{ [1,2] [1] [2] []
for (int j = 0; j < size; j++)
[1,2,3] [1,2] [1,3] [2,3] [3] []
cout << ans[j] << " " << endl;
[1] [2]

Base cases (Final Subsets)

return;
}
 ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
Printing all the Subsets
printSubsets( arr, n, i + 1, ans, size );

Condition for Base case (i = n)

if (i == n)
{
for (int j = 0; j < size; j++)
cout << ans[j] << " " << endl;
return;
} After printing one subset,
the control returns back
one node
 ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
Printing all the Subsets
printSubsets( arr, n, i + 1, ans, size );

if (i == n)
{
for (int j = 0; j < size; j++)
cout << ans[j] << " " << endl;
return;
}
 ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);
Printing all the Subsets
printSubsets( arr, n, i + 1, ans, size );

if (i == n)
{
for (int j = 0; j < size; j++)
cout << ans[j] << " " << endl;
return;
}
 if (i == n)
Printing all the Subsets {
for (int j = 0; j < size; j++)
cout << ans[j] << " " << endl;
return;
}
ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);

printSubsets( arr, n, i + 1, ans, size );

Printing all the Subsets

if (i == n)
{
for (int j = 0; j < size; j++)
cout << ans[j] << " " << endl;
return;
}
ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);

printSubsets( arr, n, i + 1, ans, size );

Printing all the Subsets
void printSubsets(int arr[], int n, int i, int ans[], int size)
{
if (i == n) // base case when i = n
{
for (int j = 0; j < size; j++)
cout << ans[j] << " " << endl; Final Algorithm
return;
}
To Print all the Subsets

ans[size] = arr[i]; // include

printSubsets(arr, n, i + 1, ans, size + 1);

printSubsets( arr, n, i + 1, ans, size ); // exclude

}
 To find Solution to the actual Problem i.e.

Finding Subsets where Sum of Elements Equals Target

We Modify the previous Algorithim
Subsets where Sum Equals to the Target

void printSubsets(int arr[], int n, int i, int ans[], int size)

{
if (i == n)
{
for (int j = 0; j < size; j++)
cout << ans[j] << " " << endl;
return; This Algorithm becomes...
}
ans[size] = arr[i];
printSubsets(arr, n, i + 1, ans, size + 1);

printSubsets( arr, n, i + 1, ans, size );

}
Subsets where Sum Equals to the Target
void subsetSum(int arr[], int n, int i, int ans[], int size, int sum, int target)
{
if (i == n) // base case
{
if (sum == target)
{
for (int j = 0; j < size; j++)

This
cout << ans[j] << " " << endl;
}
return;
}

ans[size] = arr[i]; // include

subsetSum(arr, n, i + 1, ans, size + 1, sum + arr[i], target);

subsetSum(arr, n, i + 1, ans, size, sum, target); // exclude

}
Subsets where Sum Equals to the Target
void subsetSum(int arr[], int n, int i, int ans[], int size, int sum, int target)
{ Two extra Parameters
if (i == n) // base case are introduced
{
if (sum == target)
{
for (int j = 0; j < size; j++)
cout << ans[j] << " " << endl;
}
return;
}

ans[size] = arr[i]; // include

subsetSum(arr, n, i + 1, ans, size + 1, sum + arr[i], target);

subsetSum(arr, n, i + 1, ans, size, sum, target); // exclude

}
Subsets where Sum Equals to the Target
void subsetSum(int arr[], int n, int i, int ans[], int size, int sum, int target)
{ Two extra Parameters
if (i == n) // base case are introduced
{
if (sum == target)
{ Base Subset printed only when the
for (int j = 0; j < size; j++) Sum Equals the Target
cout << ans[j] << " " << endl;
}
return;
}

ans[size] = arr[i]; // include

subsetSum(arr, n, i + 1, ans, size + 1, sum + arr[i], target);

subsetSum(arr, n, i + 1, ans, size, sum, target); // exclude

}
Subsets where Sum Equals to the Target
void subsetSum(int arr[], int n, int i, int ans[], int size, int sum, int target)
{ Two extra Parameters
if (i == n) // base case are introduced
{
if (sum == target)
{ Base Subset printed only when the
for (int j = 0; j < size; j++) Sum Equals the Target
cout << ans[j] << " " << endl;
}
return; As Sum is being Calculated it is also
} being passed for next Recursive call
ans[size] = arr[i]; // include
subsetSum(arr, n, i + 1, ans, size + 1, sum + arr[i], target);

subsetSum(arr, n, i + 1, ans, size, sum, target); // exclude

}
Complexities
Time Complexity
Time Complexity
[]
[1] []

[1,2] [1] [2] []

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

2ⁿ Subsets
Time Complexity 1st

[]
[1] []

[1,2] [1] [2] []

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

2ⁿ Subsets
Time Complexity 1st

[]
2nd
[1] []

[1,2] [1] [2] []

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

2ⁿ Subsets
Time Complexity 1st

[]
In this case a
Total of ‘3’
2nd
[1] []
steps for each
Subset
3rd [1,2] [1] [2] []

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

Total of ‘n’
steps to reach
the Base
2ⁿ Subsets
Time Complexity 1st

[]
2nd
[1] []

3rd [1,2] [1] [2] []

[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

Total of ‘n’
steps to reach
the Base
2ⁿ Subsets

So total Calls : n x 2ⁿ
Time Complexity : O(n2ⁿ)
Space Complexity
Space Complexity

Depends on these 2 :

(Recursion stack + temporary array)

Space Complexity

Depends on these 2 :

(Recursion stack + temporary array)

Maximum depth of ans[] stores at most

recursion = n n elements
Space Complexity

Depends on these 2 :

(Recursion stack + temporary array)

Maximum depth of ans[] stores at most

recursion = n n elements

So, Space Complexity : O(n)

 Thank You

while(noSuccess) {
tryAgain();

if(dead)
break;
}