Dynamic Programming: Count of subset sum with a given sum

Problem Statement:

You are given an array and a sum,you need to find the number of subsets with that sum.

Example

Input: arr[] = {1, 2, 3, 3}, sum = 6
Output: 3

All the possible subsets are {1, 2, 3}, {1, 2, 3} and {3, 3}

Solution

This problem is similar to the parent problem 0/1 knapsack and very much similar to subset sum problem.

In this problem we are given an array and a sum value, we need to find out the number of subset with that sum.

So for every element we have two choices, either we take that element or leave that element.

Before we go to the tabulation method, we will first see the recurrence relation.

1. Recursion

As mentioned earlier, at every element we have an option to choose the element or ignore that element.

Case 1: If we choose the element, then we subtract that element value from the sum.

Case 2: If we ignore the element, then we move to the next element.

It can be written as:
count = get_subset_count(arr, n, i + 1, sum – arr[i], count);
count = get_subset_count(arr, n, i + 1, sum, count);

at every step, we will get the count, and return the final count

Base case will be, if we reach at the end of the array and the sum == 0, then increment the count.

if (i == n) {
    if (sum == 0)
        count++;
    return count;
}

2. Tabulation

Instead of taking boolean 2D array, as we need count, we will take int array.

At the end we will get the final count.

As we need the count we need to add the result instead of “or” used in subset sum.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_set> 
#include <list> 

using namespace std;

int get_subset_sum_recursion(int arr[], int n, int i, int sum, int count)
{
    if (i == n) {
        if (sum == 0) {
            count++;
        }
        return count;
    }
  
    count = get_subset_sum_recursion(arr, n, i + 1, sum - arr[i], count);
    count = get_subset_sum_recursion(arr, n, i + 1, sum, count);
    return count;
}

int get_subset_sum_tabulation(int arr[], int n, int sum) 
{
    int DP[n + 1][sum + 1];
    DP[0][0] = 1;
    for (int i = 1; i <= sum; i++)
        DP[0][i] = 0;
    for (int i = 1; i <= n; i++)
        DP[i][0] = 1;
 
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= sum; j++)
        {
          // if the value is greater than the sum
            if (arr[i - 1] > j)
                DP[i][j] = DP[i - 1][j];
            else
            {
                DP[i][j] = DP[i - 1][j] + DP[i - 1][j - arr[i - 1]];
            }
        }
    }
    return DP[n][sum];
}

int main()
{
    int set[] = {1, 5, 11, 5};
    int sum = 6;
    int n = sizeof(set) / sizeof(set[0]);
 
      cout << "Subset sum count using recursion "<< get_subset_sum_recursion(set, n, 0, sum, 0)<<endl;
      cout << "Subset sum count using tabulation "<<get_subset_sum_tabulation(set, n, sum)<<endl;

    return 0;
}

Output:

Subset sum count using recursion 2
Subset sum count using tabulation 2
Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *