Find number of subsets with sum divisible by given number M

Reading time: 30 minutes | Coding time: 10 minutes

In this problem, we will be given an array A[0.....N-1] and a number m and we have to find count of subsets whose sum is divisible by m.

Consider our array A={1,2,2} and m=2

There are 8 different subsets like {}, {1}, {2}, {2}, {1, 2}, {2, 2}, {1, 2}, (1, 2, 2}

Subsets with sum divisible by m (2) are: {}, {2}, {2}, {2,2}
Number of subsets with sum divisible by m (2) is 4

We will solve this using a Dynamic Programming approach with time complexity O(N * M).

Naive Approach

In naive approach we find all the subsets of the given array by recursion and find sum of all possible subsets and count how many sum values are divisible by m.If the sum of any two subsets is same we have to count the frequency of such a value and add it to the answer.

The time complexity of such a technique is O(2^length) where length signifies the length of the given array.

Dynamic Programming Approach

We use Dynamic Programming algorithm to solve this problem efficiently.
The working will be little different from what it was in the problem Find if there exists a subset with sum divisible by m.

In the table DP[i][j] signifies number of subsets with sum 'j' till the elements from 1st to ith are taken into consideration.

DP[i][j] = number of subsets with sum 'j' till the elements from 1st to ith

Basic Idea

We first find the total sum of all the array elements,the sum of any subset will be less than or equal to that value. So we make an array DP[sum+2][length+2] as in the 0th row we will fill the possible sum values and in the 0th column we will fill the array values and initialize it with value'0'.

We fill the column-'1' of all the rows with value 1 as there is always a subset with sum value='0' and then for each array element we find if the above row has that particular sum value not equal to zero we add that element to that sum and in the cell of the resultant sum we update it's value by the sum of its previous frequency and frequency value of the particluar sum value.

Intuitive idea

For a particular array element i if DP[i-1][j] is not equal to zero the then we update the value of DP[i][j+arr[i]] by sum of DP[i-1][j+arr[i]] and DP[i-1][j].At last we check in the last row and if column number is divisible by m then add that value to ans.

Example:

A={1,2,2}
m=2
Subsets are-{2},{2},{2,2},{}
Subset count is 4

Explanation of given example by DP table-:

0	0	1	2	3	4	5
0	1	0	0	0	0	0
1	1	0	0	0	0	0
2	1	0	0	0	0	0
2	1	0	0	0	0	0

(1) We initialize the entire DP table with value 0 initially, and then fill the first column with value 1 which indicates the presence of null set whose sum value is 0.

0	0	1	2	3	4	5
0	1	0	0	0	0	0
1	1	1	0	0	0	0
2	1	0	0	0	0	0
2	1	0	0	0	0	0

(2) For first element 1 of the array we get that sum=0 already exists so we go to sum=1 column i.e. DP[2][2] and replace the value with sum of DP[1][2] and DP[1][1] which means that frequency of subsets with sum=1 will be the sum of already occuring subsets with sum=1 and subsets with sum=0.

0	0	1	2	3	4	5
0	1	0	0	0	0	0
1	1	1	0	0	0	0
2	1	1	1	1	0	0
2	1	0	0	0	0	0

(3) For second element 2 of the array we get that sum=0 already exists so we go to sum=2 column i.e DP[3][3] and replace it with value of sum of DP[2][3] and DP[2][1].Then we further traverse in above row and find that subset with sum=1 already exists so we go to sum=3 column and replace it with sum of DP[2][4] and DP[2][2] which means subsets with sum=3 will be the sum of already occuring subsets with sum=3 and subsets with sum=0.

0	0	1	2	3	4	5
0	1	0	0	0	0	0
1	1	1	0	0	0	0
2	1	1	1	1	0	0
2	1	1	2	2	1	1

(4) In same way we find which subset sum has what frequency for every element of the given array.At last in the last row we have all the possible sums and there frequencies,then we traverse the last row and find if the particular sum value is divisble by m.

0	0	1	2	3	4	5
0	1	0	0	0	0	0
1	1	1	0	0	0	0
2	1	1	1	1	0	0
2	1	1	2	2	1	1

(5) While traversing the last row we find that out of all possible sum values {0,2,4} are the values which are divisible by 2,so we check in the column having sum=0 that is 1, sum=2 that is 2,sum=4 that is 1 so answer is 4.

Pseudo Code

for(i from 0 to n)
sum+=arr[i];

DP[sum+2][length+2]={0};
for(j=1;j<=length+1;j++)
{
  DP[j][1]=1;
  if(j-2>=0)
  DP[j][0]=arr[j-2];
}
for(j=1;j<=sum+1;j++)
{
 DP[0][j]=j-1;
}

for(i=2 to length+1)
{
  for(j=1;j<=sum+1;j++)
  {
    if(DP[i-1][j]!=0)
    {
      DP[i][j-1+arr[i-2]]=DP[i-1][j-1+arr[i-2]]+DP[i-1][j-1];
    }
  }
 }
 
 for(i=1;i<=sum+1;i++)
 {
   if((i-1)%m=0)
   {
    ans+=DP[length+1][i-1];
   }
  }

C++ Implementation

Following is the C++ implementation:

   #include<bits/stdc++.h>
   using namespace std;
   #define ll long long int
   int main()
   {
    ll arr[]={2,3,3,1};
    ll l=4;
    ll m=6;
    ll i,j,sum=0,ans=0;
 

    //Calculating the maximum possible sum
    for(i=0;i<l;i++)
    {
     sum+=arr[i];
    }

    ll DP[l+2][sum+2];
    for(i=0;i<l+2;i++)
    {
      for(j=0;j<sum+2;j++)
      {
      DP[i][j]=0;
      }
     }
 

    //Filling 0th row of the table
    //With all possible sum values
    for(j=1;j<sum+2;j++)
    {
     DP[0][j]=j-1;
    }

    //Filling 0th column 
    //With all the array values
   DP[1][0]=0;
   for(j=2;j<l+2;j++)
   {
   DP[j][0]=arr[j-2];
   }

   //Filling 1st column 
   //Where sum value=0 with all 1's
   for(i=1;i<l+2;i++)
   {
   DP[i][1]=1;
   } 
 

   //Filling the DP table
   //according to given logic
   for(i=2;i<l+2;i++)
   {
     for(j=1;j<sum+2;j++)
     {      
      if(DP[i-1][j]!=0)
      {
       DP[i][j+arr[i-2]]=DP[i-1][j+arr[i-2]]+DP[i-1][j];
      }
     }
     for(j=1;j<sum+2;j++)
     {
      DP[i][j]=max(DP[i-1][j],DP[i][j]); 
     }  
    }
 

   //counting the number of values
   //divisible by m
   for(j=1;j<sum+2;j++)
   {
    if((j-1)%m==0)
    ans+=DP[l+1][j];
  
   }
   cout<<"Number of subsets is:"<<ans<<"\n";
   return 0;
   }

Output-:

Number of subsets is:4

Time Complexity

Time complexity of Dynamic Programming approach will be O(sum * length) where sum is the total possible sum and length is the number of elements in the array.

HAPPY CODING!