New paste
Recent API Trending Blog
Guest
 
shriyanshi24jindal

Partitions with Given Difference

shriyanshi24jindal
Mar 28th, 2026
14
0
Never
Not a member of GistPad yet? Sign Up, it unlocks many cool features!
Java 25.05 KB | None | 0 0
copy raw download clone embed print report
  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. }
RAW Paste Data Copied
Public Pastes
Hello
Not a member of Fast Pastebin Alternative yet?
Sign Up, it unlocks many cool features!
 
We use cookies for various purposes including analytics. By continuing to use Fast Pastebin Alternative, you agree to our use of cookies as described in the Privacy Policy.  OK, I Understand