{"id":892,"date":"2025-08-13T19:32:54","date_gmt":"2025-08-13T14:02:54","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=892"},"modified":"2025-08-13T19:32:55","modified_gmt":"2025-08-13T14:02:55","slug":"partitions-with-given-difference","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/partitions-with-given-difference\/","title":{"rendered":"Partitions with Given Difference | Optimal Solution"},"content":{"rendered":"\n

Given an array arr[]<\/strong>, partition it into two subsets(possibly empty) such that each element must belong to only one subset. Let the sum of the elements of these two subsets be sum1<\/strong> and sum<\/strong>2<\/strong>. Given a difference d<\/strong>, count the number of partitions in which sum<\/strong>1<\/strong> is greater than or equal to sum<\/strong>2<\/strong> and the difference between sum<\/strong>1<\/strong> and sum<\/strong>2<\/strong> is equal to d<\/strong>. <\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

Examples :<\/strong><\/p>\n\n\n\n

Input: <\/strong>arr[] =  [5, 2, 6, 4], d = 3\nOutput: <\/strong>1\nExplanation: <\/strong>There is only one possible partition of this array. Partition : {6, 4}, {5, 2}. The subset difference between subset sum is: (6 + 4) - (5 + 2) = 3.<\/pre>\n\n\n\n
Input:<\/strong> arr[] = [1, 1, 1, 1], d = 0 
Output:<\/strong> 6 
Explanation: <\/strong>We can choose two 1's from indices {0,1}, {0,2}, {0,3}, {1,2}, {1,3}, {2,3} and put them in sum1 and remaning two 1's in sum2.
Thus there are total 6 ways for partition the array arr. <\/pre>\n\n\n\n
Input:<\/strong> arr[] = [1, 2, 1, 0, 1, 3, 3], d = 11
Output:<\/strong> 2<\/pre>\n\n\n\n
Constraint:<\/strong>
1 <= arr.size() <= 50
0 <= d  <= 50
0 <= arr[i] <= 6<\/p>\n\n\n\n
\n\n\n\n
Problem-to-Subset-Sum Reduction<\/h2>\n\n\n\n
Given an array arr, split it into two subsets S1 and S2 such that:<\/p>\n\n\n\n