Subset Sum using Dynamic Programming
Prerequisite –Tutorial 1,Tutorial 2
Problem Statement-
Given a array
of integer you have to tell if there is subset present in array which have the
sum equal to given array.
Eg.arr[]=[2,3,7,8,10]
Sum=11
Output -Yes
Sumset={3,8}
Parent
Problem-
0-1 knapsack
how it is related to 0-1 knapsack?
I want to tell
again that we try to drive solution of child problem from parent problem.In
this problem we can choose a element or not and any where if this type of pattern
trigger then surely that problem can be solved using 0-1 knapsack pattern.And
as we forward in tutorial you can easily find.
Choice diagram of subset sum
Choice diagram of 0-1 knapsack
How to
identify Dynamic Programming-
1.choice –
In this
problem you can choose a element or not.Condition 1 is satisfied.
2.Optimal-
In this
problem you can’t see the maximum or minimum don’t worry now assign 1 to yes
and 0 to No then you want to yes mean you try to find maximum.Condition 2 is satisfied.
How to fill Table?
1.base
condition
If i==0 and
j==0 means you have to find sum equal to zero and you have empty array can you
find ?
Yes there
will be an empty subset.
If j==0 then
for i=1 to n means you have to find sum equal
to zero and you have non empty array can you find yes there will be an empty subset.
If i==0 then
for j=1 to Sum means you have to find non zero sum but you have empty array can
you find? No
2.Choice
diagram
If you choose
element for example 3 then you look for 11-3=8 if there is possible to any
subset which is equal to 8
dp[i][j]=dp[i-1][j-arr[i-1] or dp[i-1][j]
If you does
not choose
dp[i][j]=dp[i-1][j]
0 1 2 3 4 5 6
7 8
9 10 11
|
T |
F |
F |
F |
F |
F |
F |
F |
F |
F |
F |
F |
|
T |
F |
Dp[i-1][2-2]||F==T||F==T |
Dp[i-1][3-2]||F==F |
F |
F |
F |
F |
F |
F |
F |
F |
|
T |
F |
T |
DP[i-1][3-3]||F=T |
F |
DP[i-1][5-3]||F=T |
F |
F |
F |
F |
F |
F |
|
T |
F |
T |
T |
F |
T |
F |
T |
F |
T |
T |
F |
|
T |
F |
T |
T |
F |
T |
F |
T |
T |
T |
T |
T |
|
T |
F |
T |
T |
F |
T |
F |
T |
T |
T |
T |
T |
Left side
from row 0 to row 5 =[2,3,7,8,10]
Difference
in code (Bottom UP)
|
0-1 knapsack |
Subset sum |
|
dp[i][j]=0; else if(weight[i-1]<=j) dp[i][j]=max(value[i-1]+dp[i-1][j-weight[i-1]],dp[i-1][j]); else dp[i][j]=dp[i-1][j]; |
dp[i][j]=true; else if(j==0) dp[i][j]=false; else if(arr[i-1]<=j) dp[i][j]=(dp[i-1][j-arr[i-1]]||dp[i-1][j]); else dp[i][j]=dp[i-1][j]; |
Where to
practice-
https://practice.geeksforgeeks.org/problems/subset-sum-problem/0
Code-
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n],sum=0;
for(int i=0;i<n;i++)
{ cin>>arr[i];
sum+=arr[i];
}
if(sum%2!=0)
cout<<"NO\n";
else
{
sum=sum/2;
bool dp[n+1][sum+1];
for (int i = 0; i <= n; i++)
{dp[i][0] = true;
}
for (int i = 1; i <= sum; i++)
dp[0][i] = false;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=sum;j++)
{
if(i==0)
dp[i][j]=true;
else if(j==0)
dp[i][j]=false;
else if(arr[i-1]<=j)
dp[i][j]=(dp[i-1][j-arr[i-1]]||dp[i-1][j]);
else
dp[i][j]=dp[i-1][j];
}
}
if(dp[n][sum]==true)
cout<<"YES\n";
else
cout<<"NO\n";
}
}
}
Time complexity
O(n*Sum)
Space complexity
O(n*Sum)
