Count of subsets of a given sum

Problem Link: GFG - Perfect Sum Problem

Problem Statement:
Given an array arr[] of non-negative integers and an integer sum, count all subsets of the given array with a sum equal to sum. The answer may be large, so return it modulo 109+710^9 + 7.

Note: Two subsets are considered different if they have different indices of elements, even if the elements themselves are the same.

Solution Flow

Recursion → Memoization → Tabulation → Space Optimization

1. Recursion (Pick-Not Pick Approach)

Intuition:
Try including or excluding each element. Count all valid subsets where sum reaches exactly 0.

Base Cases:

If sum == 0, return 1 (found a valid subset).
If n == 0, return 0 (no elements left to choose from).

Java Code:

class Solution {
    static int mod = 1000000007;

    public int perfectSum(int arr[], int n, int sum) {
        return recursion(arr, n, sum);
    }

    private int recursion(int arr[], int n, int sum) {
        if (n == 0) return (sum == 0) ? 1 : 0;

        int exclude = recursion(arr, n-1, sum) % mod;
        int include = 0;
        if (arr[n-1] <= sum)
            include = recursion(arr, n-1, sum - arr[n-1]) % mod;

        return (exclude + include) % mod;
    }
}

Complexity:

Time: O(2n)O(2^n)
Space: O(n)O(n)

2. Memoization (Top-Down DP)

Java Code:

class Solution {
    static int mod = 1000000007;

    public int perfectSum(int arr[], int n, int sum) {
        int[][] dp = new int[n+1][sum+1];
        for (int[] row : dp) Arrays.fill(row, -1);
        return memo(arr, n, sum, dp);
    }

    private int memo(int arr[], int n, int sum, int[][] dp) {
        if (n == 0) return (sum == 0) ? 1 : 0;
        if (dp[n][sum] != -1) return dp[n][sum];

        int exclude = memo(arr, n-1, sum, dp) % mod;
        int include = 0;
        if (arr[n-1] <= sum)
            include = memo(arr, n-1, sum - arr[n-1], dp) % mod;

        return dp[n][sum] = (exclude + include) % mod;
    }
}

Complexity:

Time: O(n×sum)O(n \times \text{sum})
Space: O(n×sum)O(n \times \text{sum})

3. Tabulation (Bottom-Up DP)

Java Code:

class Solution {
    static int mod = 1000000007;

    public int perfectSum(int arr[], int n, int sum) {
        int[][] dp = new int[n+1][sum+1];

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

        for (int i = 1; i <= n; i++) {
            for (int s = 0; s <= sum; s++) {
                dp[i][s] = dp[i-1][s] % mod;
                if (arr[i-1] <= s)
                    dp[i][s] = (dp[i][s] + dp[i-1][s - arr[i-1]]) % mod;
            }
        }
        return dp[n][sum];
    }
}

Dry Run Example:
Input: arr = [2, 3, 5, 6, 8, 10], sum = 10

`i`	`s`	`dp[i][s]`	Reason
1	2	1	dp[0][2] = 0 + dp[0][0] = 1
2	5	1	dp[1][5] = 0 + dp[1][2] = 1
3	10	1	dp[2][10] = 0 + dp[2][5] = 1
4	10	2	dp[3][10] = 1 + dp[3][4] = 1
6	10	3	Final result after all iterations

Output: 3
Valid subsets: [2,3,5], [2,8], [10]

4. Space Optimization (1D DP)

Java Code:

class Solution {
    static int mod = 1000000007;

    public int perfectSum(int arr[], int n, int sum) {
        int[] dp = new int[sum+1];
        dp[0] = 1;

        if (arr[0] <= sum)
            dp[arr[0]] = (dp[arr[0]] + 1) % mod;

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

Dry Run Example:
Input: arr = [0, 0, 1], sum = 1

Step-by-step state of dp[]:

arr[0] = 0
dp[0] = 1 + 1 = 2 → {}, {0}
arr[1] = 0
dp[0] = 2 + 2 = 4 → {}, {0}, {0}, {0,0}
arr[2] = 1
dp[1] = 0 + dp[0] = 4

Final Output: 4
Subsets: [1], [0,1], [0,1], [0,0,1]

Key Insights

Subset Count with Exact Sum:
Classic variant of 0/1 Knapsack but counts total ways, not just yes/no.
Zero Elements:
Every zero doubles the number of valid subsets because it can be included or excluded without affecting the sum.
Space Optimization:
Use reverse loop when working with 1D array to avoid overwriting needed values.
Edge Cases:
- All zeros → 2k2^k subsets sum to 0 (where kk is count of zeros).
- Use modulo 109+710^9 + 7 to avoid overflow.

Interview Tip: Always show recursion → memoization → tabulation → space optimization, and explain time/space trade-offs.