1. class Solution {
  2.  
  3.     /** Recursive code */
  4.     static Boolean isSubsetSum(int arr[], int sum) {
  5.         int n = arr.length;
  6.         return findSubsetSum(arr, sum, n);
  7.     }
  8.  
  9.     static Boolean findSubsetSum(int[] arr, int sum, int n)
  10.     {
  11.         // when we reach end of the array, so couldn't found a subset
  12.         if(n == 0)
  13.             return false;
  14.  
  15.         // when sum becomes 0 that means found a subset
  16.         if(sum == 0)
  17.             return true;
  18.  
  19.         if(arr[n-1] <= sum)
  20.         {
  21.             // pick the element in subset
  22.             boolean pick = findSubsetSum(arr, sum - arr[n-1], n-1);
  23.             // do not pick the element in subset
  24.             boolean notPick = findSubsetSum(arr, sum, n-1);
  25.             return pick || notPick;
  26.         }
  27.         // when current element exceeds given sum, so skip the element
  28.         return findSubsetSum(arr, sum, n-1);
  29.     }
  30.  
  31.     /** Memoization code */
  32.     static Boolean isSubsetSum(int arr[], int sum) {
  33.         int n = arr.length;
  34.  
  35.         boolean[][] t = new boolean[n+1][sum+1];
  36.         // when array of size will increase but sum needs to always 0, then we can have always empty subset
  37.         for(int i=0; i<n+1; i++)
  38.         {
  39.             Arrays.fill(t[i], true);
  40.         }
  41.  
  42.         // when sum increases but size of array is always 0, then we cannot have any subset
  43.         for(int j=0; j<n+1; j++)
  44.         {
  45.             Arrays.fill(t[j], false);
  46.         }
  47.  
  48.         return findSubsetSum(arr, sum, n, t);
  49.     }
  50.  
  51.     static Boolean findSubsetSum(int[] arr, int sum, int n, boolean[][] t)
  52.     {
  53.         // when we reach end of the array, so couldn't found a subset
  54.         if(n == 0)
  55.             return false;
  56.  
  57.         // when sum becomes 0 that means found a subset
  58.         if(sum == 0)
  59.             return true;
  60.  
  61.         if(t[n][sum] != false)
  62.             return t[n][sum];
  63.  
  64.         if(arr[n-1] <= sum)
  65.         {
  66.             // pick the element in subset
  67.             boolean pick = findSubsetSum(arr, sum - arr[n-1], n-1, t);
  68.             // do not pick the element in subset
  69.             boolean notPick = findSubsetSum(arr, sum, n-1, t);
  70.             t[n][sum] = pick || notPick;
  71.             return t[n][sum];
  72.         }
  73.         // when current element exceeds given sum, so skip the element
  74.         t[n][sum] = findSubsetSum(arr, sum, n-1, t);
  75.         return t[n][sum];
  76.     }
  77.  
  78.     /** Top-down approach */
  79.     static Boolean isSubsetSum(int arr[], int sum) {
  80.         int n = arr.length;
  81.  
  82.         boolean[][] t = new boolean[n+1][sum+1];
  83.  
  84.         // intialise the matrix on basis of base condition
  85.         for(int i=0; i<n+1; i++)
  86.         {
  87.             for(int j=0; j<sum+1; j++)
  88.             {
  89.                 // when sum increases but size of array is always 0, then we cannot have any subset
  90.                 if(i==0)
  91.                 {
  92.                     t[i][j] = false;
  93.                 }
  94.                 // when array of size will increase but sum needs to always 0, then we can have always empty subset
  95.                 if(j==0)
  96.                 {
  97.                      t[i][j] = true;
  98.                 }
  99.             }
  100.         }
  101.  
  102.         for(int i=1; i<n+1; i++)
  103.         {
  104.             for(int j=1; j<sum+1; j++)
  105.             {
  106.                 if(arr[i-1] <= j)
  107.                 {
  108.                     boolean pick = t[i-1][j - arr[i-1]];
  109.                     boolean notPick = t[i-1][j];
  110.                     t[i][j] = pick || notPick;
  111.                 }
  112.                 else
  113.                     t[i][j] = t[i-1][j];
  114.             }
  115.         }
  116.         return t[n][sum];
  117.     }
  118. }