Count Partitions with Given Difference
DP on Subsequences DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Count Partitions with Given Difference, Dynamic Programming, Memoization, Tabulation, Space Optimization, Recursion, Subsequences, Subset Sum, Arrays, Time Complexity, Space Complexity, Mathematical Algorithms, Conditional Statements, Loops, Absolute Difference, edge cases, dynamic programming, memoization, combinatorics, tabulation, space optimization, recursion.
Count Partitions with Given Difference Given an array ARR of N non negative integers and an integer D. We need to count the number of ways to partition the given array into two subsets, S1 and S2, such that the sum of elements in S1 minus the sum of elements in S2 equals D. That is, sum(S1) sum(S2) = D, and sum(S1) must be greater than or equal to sum(S2). Input Specification: The first line contains an integer N, representing the size of the array. The second line contains N space separated non negative integers, representing the elements of the array ARR. The third line contains an integer D, representing the required difference. Output Specification: Print a single integer, the number of ways to partition the array into two subsets satisfying the given conditions. Constraints: The array elements can be 0 or positive. The sum of elements can be up to approximately 10^5. Sample Input: Sample Output: Explanation: The array is {5, 2, 6, 4} and the difference D is 3. The total sum of elements is 5 + 2 + 6 + 4 = 17. We need to find S2 such that 2 S2 = (totalSum D). Substituting values, 2 S2 = (17 3) = 14, so S2 = 7. Now, we need to find the number of subsets with sum 7. The subset {2, 5} sums to 7, which gives S1 = {6, 4} (sum = 10). 10 7 = 3. This is one way. There are no other subsets that sum to 7. Difficulty: Medium