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