Perfect Sum Problem

Given an array arr[] of non-negative integers and an integer sum, the task is to count all subsets of the given array with a sum equal to a given sum.

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

class Solution {

public:
    int perfectSum(int arr[], int n, int sum) {
        int mod = 1e9 + 7;
        vector<int> dp(sum + 1);
        dp[0] = 1;

        for(int i = 0; i < n; i++) {
            for(int j = sum; j >= arr[i]; j--) {
                dp[j] = (dp[j] + dp[j-arr[i]]) % mod;
            }
        }

        return dp[sum] % mod;
    }