1. class Solution {
  2.     // Similar to Count of partitions with given difference
  3.  
  4.     /** Recursive code */
  5.     public int findTargetSumWays(int[] arr, int target) {
  6.         int n = arr.length;
  7.  
  8.         int totalSum = 0;
  9.         for(int ele : arr)
  10.             totalSum += ele;
  11.  
  12.         // target cannot be larger than possible sum range
  13.         if(Math.abs(target) > totalSum)
  14.             return 0;
  15.  
  16.         // we can't divide if sum is not even
  17.         if( (totalSum+target) % 2 != 0)
  18.             return 0;
  19.  
  20.         int sum = (totalSum+target)/2;
  21.  
  22.         return findSubsetSum(arr, sum, n);
  23.     }
  24.  
  25.     public int findSubsetSum(int[] arr, int sum, int n)
  26.     {
  27.         if(n == 0)
  28.         {
  29.             if(sum == 0)
  30.                 return 1;
  31.             return 0;
  32.         }
  33.  
  34.         if(arr[n-1] <= sum)
  35.         {
  36.             int pick = findSubsetSum(arr, sum - arr[n-1], n-1);
  37.             int notPick = findSubsetSum(arr, sum, n-1);
  38.             return pick + notPick;
  39.         }
  40.         return findSubsetSum(arr, sum, n-1);
  41.     }
  42.  
  43.     /** Memoization code */
  44.     public int findTargetSumWays(int[] arr, int target) {
  45.         int n = arr.length;
  46.  
  47.         int totalSum = 0;
  48.         for(int ele : arr)
  49.             totalSum += ele;
  50.  
  51.         // target cannot be larger than possible sum range
  52.         if(Math.abs(target) > totalSum)
  53.             return 0;
  54.  
  55.         // we can't divide if sum is not even
  56.         if( (totalSum+target) % 2 != 0)
  57.             return 0;
  58.  
  59.         int sum = (totalSum+target)/2;
  60.  
  61.         int[][] t = new int[n+1][sum+1];
  62.  
  63.         for(int i=0; i<n+1; i++)
  64.             Arrays.fill(t[i], -1);
  65.  
  66.         return findSubsetSum(arr, sum, n, t);
  67.     }
  68.  
  69.     public int findSubsetSum(int[] arr, int sum, int n, int[][] t)
  70.     {
  71.         if(n == 0)
  72.         {
  73.             if(sum == 0)
  74.                 return 1;
  75.             return 0;
  76.         }
  77.  
  78.         if(t[n][sum] != -1)
  79.             return t[n][sum];
  80.  
  81.         if(arr[n-1] <= sum)
  82.         {
  83.             int pick = findSubsetSum(arr, sum - arr[n-1], n-1, t);
  84.             int notPick = findSubsetSum(arr, sum, n-1, t);
  85.             t[n][sum] = pick + notPick;
  86.             return t[n][sum];
  87.         }
  88.         t[n][sum] = findSubsetSum(arr, sum, n-1, t);
  89.         return t[n][sum];
  90.     }
  91.  
  92.     /** Top-down approach */
  93.     public int findTargetSumWays(int[] arr, int target) {
  94.         int n = arr.length;
  95.  
  96.         int totalSum = 0;
  97.         for(int ele : arr)
  98.             totalSum += ele;
  99.  
  100.         // target cannot be larger than possible sum range
  101.         if(Math.abs(target) > totalSum)
  102.             return 0;
  103.  
  104.         // we can't divide if sum is not even
  105.         if( (totalSum+target) % 2 != 0)
  106.             return 0;
  107.  
  108.         int sum = (totalSum+target)/2;
  109.  
  110.         int[][] t = new int[n+1][sum+1];
  111.  
  112.         for(int i=0; i<n+1; i++)
  113.         {
  114.             for(int j=0; j<sum+1; j++)
  115.             {
  116.                 // when array is empty
  117.                 if(i == 0)
  118.                     t[i][j] = 0;
  119.  
  120.                 // when sum is always 0
  121.                 if(j == 0)
  122.                     t[i][j] = 1;
  123.             }
  124.         }
  125.  
  126.         for(int i=1; i<n+1; i++)
  127.         {
  128.             for(int j=0; j<sum+1; j++)
  129.             {
  130.                 if(arr[i-1] <= j)
  131.                 {
  132.                     int pick = t[i-1][j - arr[i-1]];
  133.                     int notPick = t[i-1][j];
  134.                     t[i][j] = pick + notPick;
  135.                 }
  136.                 else
  137.                     t[i][j] = t[i-1][j];
  138.             }
  139.         }
  140.  
  141.         return t[n][sum];
  142.     }
  143. }