Skip to main content

Subset Sum In Dynamic Programming

Subset Sum using Dynamic Programming

DP Tutorial 3

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

                     if(i==0||j==0)

    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];

                      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];

 

Where to practice-

https://practice.geeksforgeeks.org/problems/subset-sum-problem/0

Code-

 #include <iostream>

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)

Comments

Popular posts from this blog

Create a socket for HTTP for web page upload and download

Create a socket for HTTP for web page upload and download. Aim: To write a java program for socket for HTTP for web page upload and download . Algorithm 1.Start the program. 2.Get the frame size from the user 3.To create the frame based on the user request. 4.To send frames to server from the client side. 5.If your frames reach the server it will send ACK signal to client otherwise it will send NACK signal to client. 6.Stop the program Program : Client import javax.swing.*; import java.net.*; import java.awt.image.*; import javax.imageio.*; import java.io.*; import java.awt.image.BufferedImage; import java.io.ByteArrayOutputStream; import java.io.File; import java.io.IOException; import javax.imageio.ImageIO; public class Client{ public static void main(String args[]) throws Exception{ Socket soc; BufferedImage img = null; soc=new Socket("localhost",4000); System.out.println("Client is running. ");  try { System.out.println("Reading image from disk. "); im...

Write an HTML program to design an entry form of student details and send it to store at database server like SQL, Oracle or MS Access

Write an HTML program to design an entry form of student details and send it to store at database server like SQL, Oracle or MS Access <!DOCTYPE html> <html> <head> <title>PHP insertion</title> <link href="css/insert.css" rel="stylesheet"> </head> <body> <div class="maindiv"> <!--HTML Form --> <div class="form_div"> <div class="title"> <h2>Insert Data In Database Using PHP.</h2> </div> <form action="insert.php" method="post"> <!-- Method can be set as POST for hiding values in URL--> <h2>Form</h2> <label>Name:</label> <input class="input" name="name" type="text" value=""> <label>Email:</label> <input class="input" name="email" type="text" value=""> <label>Contact:</label> <inp...

Write a code simulating PING and TRACEROUTE commands

  Write a code simulating PING command     Aim:   To Write the java program for simulating ping command   Algorithm Step 1: start the program. Step 2: Include necessary package in java. Step 3: To create a process object p to implement the ping command. Step 4: declare one BufferedReader stream class object. Step 5: Get thedetails of the server          5.1: length of the IP address.          5.2: time required to get the details.          5.3: send packets , receive packets and lost packets.          5.4: minimum ,maximum and average times. Step 6: print the results. Step 7:Stop the program.   Program:   import java.io.*; import java.net.*; class pingserver { public static void main(String args[]) { try { String str; System.out.print(" Enter...