1. class Solution {
  2.     // Function to calculate the number of subsets with a given sum
  3.     public int perfectSum(int[] nums, int target) {
  4.         int n = nums.length;
  5.  
  6.         // step-1 create a matrix
  7.         int[][] t = new int[n+1][target+1];
  8.  
  9.         // step-2 intialise the matrix with base condition
  10.         for(int i=0; i<n+1; i++)
  11.         {
  12.             for(int j=0; j<target+1; j++)
  13.             {
  14.                 // when we reach last index of the array, so no subset found
  15.                 if(i == 0)
  16.                     t[i][j] = 0;
  17.                 // when target sum becomes 0, we found a subset
  18.                 if(j == 0)
  19.                     t[i][j] = 1;
  20.             }
  21.         }
  22.  
  23.         // step-3 convert recursive code into iterative
  24.         for(int i=1; i<n+1; i++)
  25.         {
  26.             for(int j=0; j<target+1; j++)
  27.             {
  28.                 if(nums[i-1] <= j)
  29.                 {
  30.                     int pick = t[i-1][j - nums[i-1]];
  31.                     int notPick = t[i-1][j];
  32.                     t[i][j] = pick + notPick;
  33.                 }
  34.                 else
  35.                     t[i][j] = t[i-1][j];
  36.             }
  37.         }
  38.         return t[n][target];
  39.     }
  40. }