Problem Description

Given an array arr[] of length N and an integer X, the task is to find the number of subsets with sum equal to X.

Problem Link

https://www.geeksforgeeks.org/count-of-subsets-with-sum-equal-to-x/

Similarity with 0/1 Knapsack

Here the max function from 0/1 Knapsack is converted into +. Also since no val[] array is given to us hence it is omitted.

int countSubsets(int a[], int n, int sum)
{
    // Initializing the matrix
    int tab[n + 1][sum + 1];
  // Initializing the first value of matrix
    tab[0][0] = 1;
    for (int i = 1; i <= sum; i++)
        tab[0][i] = 0;
    for (int i = 1; i <= n; i++)
        tab[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 (a[i - 1] > j)
                tab[i][j] = tab[i - 1][j];
            else
            {
                tab[i][j] = tab[i - 1][j] + tab[i - 1][j - a[i - 1]];
            }
        }
    }
 return tab[n][sum];
}