Partition Set Into 2 Subsets With Min Absolute Sum Diff
DP on Subsequences DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Partition a Set Into Two Subsets With Minimum Absolute Sum Difference, Dynamic Programming, Recursion, Memoization, Tabulation, Space Optimization, Subsequences, Arrays, Time Complexity, Space Complexity, Absolute Difference, Subset Sum, bit manipulation, dynamic programming, memoization, tabulation, space optimization, recursion, time complexity analysis, DP on Subsequences / Subsets.
Problem Statement: We are given an array 'ARR' with N positive integers. We need to partition the array into two subsets such that the absolute difference of the sum of elements of the subsets is minimum. We need to return only the minimum absolute difference of the sum of elements of the two partitions. Input Specification: The first line contains an integer N, the number of elements in the array. The second line contains N positive integers representing the elements of the array ARR. Output Specification: Return a single integer representing the minimum absolute difference of the sums of the two partitions. Constraints: Constraints are not explicitly provided in the original problem description. Sample Test Cases: Example 1: Input: ARR = [1, 2, 3, 4] Output: 0 Explanation: We can partition the array into {1, 4} (sum = 5) and {2, 3} (sum = 5). The absolute difference is |5 5| = 0. Example 2: Input: ARR = [8, 6, 5] Output: 3 Explanation: We can partition the array into {8} (sum = 8) and {6, 5} (sum = 11). The absolute difference is |8 11| = 3. This is the minimum possible difference.