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