211. Partition a Set Into Two Subsets With Minimum Difference of Sums

Given an array of n non-negative integers, split it into two subsets (every element goes to exactly one subset) so as to minimize the absolute difference between the two subsets' sums. Print that minimum difference.

Input: Two lines: the first contains n, the second contains n space-separated non-negative integers. Output: Print a single integer - the minimum possible absolute difference between the two subset sums.

1 <= n <= 1000

You only need to check achievable sums up to HALF the total (not the full total) - by symmetry, any achievable sum s and its complement (total-s) represent the SAME split, so checking only up to the midpoint avoids redundant work.

Split an array into two subsets minimizing the absolute difference between their sums. Brute force: Try every possible way of splitting the array into two subsets directly - this is exponential (2^n splits), impractical for n up to 1000. Optimised: Computing which subset sums are ACHIEVABLE (a boolean DP, exactly like 0/1 knapsack's feasibility check) up to half the total lets you directly find the BEST possible split point - the closer an achievable sum is to exactly half the total, the smaller the resulting difference between the two subsets.

Try every one of the 2^n ways to assign each element to one of the two subsets, compute the sum of one subset (the other is just the total sum minus it), and track the minimum absolute difference seen. This checks every possible partition directly and is guaranteed correct, but the number of partitions doubles with every element, making it infeasible beyond small n. Time: O(2^n) Space: O(n)

Use the same subset-sum reasoning, but keep only a single 1D boolean array dp[s] of achievable sums, updating it for each element by iterating s from high (total/2) down to the element's value and setting dp[s] = dp[s] OR dp[s - a[i]] - iterating downward ensures each element is only used once per pass, reusing the previous row's values without a second dimension. After processing all elements, scan dp for the achievable sum closest to total/2 exactly as before. This keeps the same time complexity as the 2D table but reduces the memory footprint from proportional to n times the sum down to just the sum. Time: O(n * sum) Space: O(sum)

Let total be the sum of all elements. Build a 2D boolean table dp[i][s] meaning 'using only the first i elements, is sum s achievable', filled with dp[i][s] = dp[i-1][s] OR (s >= a[i] AND dp[i-1][s-a[i]]). After filling the whole table up to i = n, scan all achievable sums s up to total/2 and take the one closest to total/2; the answer is total - 2*s for the best such s. This avoids trying all 2^n partitions explicitly by reusing overlapping achievable-sum computations, at the cost of a table sized by the number of elements times the total sum. Time: O(n * sum) Space: O(n * sum)

1. Compute every ACHIEVABLE subset sum up to HALF of the total (a 0/1-knapsack-style boolean DP works well here). 2. The best split pairs the achievable subset sum CLOSEST to totalSum/2 with the rest. 3. The answer is totalSum minus TWICE that closest achievable sum.

Time: O(n * totalSum) - the boolean subset-sum DP, bounded by the array size times the total sum (or half of it). Space: O(totalSum), for the boolean achievability array.

Test n = 1 (one subset gets the whole array, the other is empty, so the difference equals the sole element) and n = 1000 with large values, since the subset-sum DP scales with the total sum.

Be ready to connect this directly to the 'Subset Sum Problem' from the Backtracking category and to 0/1 Knapsack's feasibility-checking DP - all three share the identical achievable-sums computation, just applied to slightly different final questions.