Count of subset sum with given sum

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

Prerequisite: Subset Sum Problem

• We just need to fill with int instead of bool.

• Instead of

  we have to write +

code

int countSubsetSum(int n, int arr[], int sum)
{
    int dp[n + 1][sum + 1];

    for (int i = 0; i < n + 1; i++)
        dp[i][0] = 1;

    for (int j = 1; j < sum + 1; j++)
        dp[0][j] = 0;

    for (int i = 1; i < n + 1; i++)
        for (int j = 1; j < sum + 1; j++)
            if (arr[i - 1] <= j)
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i - 1]];
            else
                dp[i][j] = dp[i - 1][j];

    return dp[n][sum];
}

Complexity Analysis

• Time Complexity: O(sum*n)
• Auxiliary Space: O(sum*n)

References

• GFG: Count of subset sum with given sum
• Youtube: AV - Count of subset sum with given sum