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

The Future of Web Development: Why Next.js is Going Viral

  Are you ready to level up your web development game? Look no further than Next.js, the latest sensation in the world of web development that's taking the industry by storm. With its powerful features, flexibility, and performance optimizations, Next.js is becoming the go-to framework for building modern web applications. In this blog post, we'll explore why Next.js is going viral and how it's changing the landscape of web development. Supercharged Performance: One of the main reasons why Next.js is making waves is its superior performance capabilities. With built-in optimizations like automatic static site generation (SSG) and server-side rendering (SSR), Next.js allows you to create blazing-fast web applications that load quickly and deliver seamless user experiences. This is especially important in today's fast-paced digital world, where users demand instant gratification and have little patience for slow-loading websites. Flexibility and Scalability: Next.js provid...

Importants Links of Leetcode

  Here are all the important discussion posts which contain brief descriptions about a topic with its problem list. Recursion:- A.   https://leetcode.com/tag/recursion/discuss/1733447/Become-Master-In-Recursion Binary Tree and Binary Search Tree:- A.   https://leetcode.com/tag/binary-tree/discuss/1212004/Binary-Trees-study-guide B.   https://leetcode.com/tag/binary-tree/discuss/1820334/Become-Master-in-Tree C.   https://leetcode.com/tag/binary-tree/discuss/1094690/Views-and-Traversal-of-binary-tree-or-Important-topics-or-Must-Read-%3A- ) Dynamic Programming:- A.   https://leetcode.com/discuss/study-guide/458695/Dynamic-Programming-Patterns B.   https://leetcode.com/tag/dynamic-programming/discuss/1437879/Dynamic-Programming-Patterns C.   https://leetcode.com/tag/dynamic-programming/discuss/662866/DP-for-Beginners-Problems-or-Patterns-or-Sample-Solutions D.   https://leetcode.com/tag/dynamic-programming/discuss/1050391/Must-do-Dynamic-programm...

Write a code simulating ARP /RARP protocols

   Write a code simulating ARP /RARP protocols . Aim:        To write a java program for simulating ARP/RARP protocols ALGORITHM: server 1. Create a server socket and bind it to port. 2. Listen for new connection and when a connection arrives, accept it. 3. Send server ‟ s date and time to the client. 4. Read client ‟ s IP address sent by the client. 5. Display the client details. 6. Repeat steps 2-5 until the server is terminated. 7. Close all streams. 8. Close the server socket. 9. Stop. Client 1. Create a client socket and connect it to the server ‟ s port number. 2. Retrieve its own IP address using built-in function. 3. Send its address to the server. 4. Display the date & time sent by the server. 5. Close the input and output streams. 6. Close the client socket. 7. Stop. Program Program for Address Resolutuion Protocol (ARP) using TCP Client: import java.io.*; import java.net.*; impor...