class Solution {
    // Function to calculate the number of subsets with a given sum
    public int perfectSum(int[] nums, int target) {
        int n = nums.length;
        
        // step-1 create a matrix
        int[][] t = new int[n+1][target+1];
        
        // step-2 intialise the matrix with base condition
        for(int i=0; i<n+1; i++)
        {
            for(int j=0; j<target+1; j++)
            {
                // when we reach last index of the array, so no subset found
                if(i == 0)
                    t[i][j] = 0;
                // when target sum becomes 0, we found a subset
                if(j == 0)
                    t[i][j] = 1;
            }
        }
        
        // step-3 convert recursive code into iterative
        for(int i=1; i<n+1; i++)
        {
            for(int j=0; j<target+1; j++)
            {
                if(nums[i-1] <= j)
                {
                    int pick = t[i-1][j - nums[i-1]];
                    int notPick = t[i-1][j];
                    t[i][j] = pick + notPick;
                }
                else
                    t[i][j] = t[i-1][j];
            }
        }
        return t[n][target];
    }
}