Log inSign up
hardGeeksforGeeksNot Started

Minimum Subset Sum Difference

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an integer array nums of non-negative integers, divide it into two subsets S1 and S2 such that the absolute difference between their sums is minimized.

Return the minimum possible absolute difference |\text{sum}(S1) - \text{sum}(S2)|.

### Example 1 - Input: nums = [1, 6, 11, 5] - Output: 1 - Explanation: - Subset 1 = [1, 5, 6], sum = 12 - Subset 2 = [11], sum = 11 - Absolute difference = |12 - 11| = 1.

### Example 2 - Input: nums = [1, 4] - Output: 3 - Explanation: Subsets are [1] and [4], difference is |4 - 1| = 3.

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 500
  • Total sum of elements <= 5 * 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Transform an optimization problem on two subsets into a single subset sum query.
  • Implement 0/1 knapsack boolean reachability.
  • Traverse the DP array backwards to achieve O(totalSum) space complexity.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Partitioning array elements into two groups to balance sums.
  • Difference minimization between two sums.

Algorithmic Decision Tree:

  • Calculate totalSum.
  • Find largest s <= totalSum / 2 that can be formed.
  • Answer is totalSum - 2 * s.

Connected Patterns:

Partition Equal Subset SumSubset SumTarget Sum

1. Recursive Inclusion / Exclusion

Intuition

Recursively branch each element into subset 1 or subset 2, tracking cumulative sums.

Algorithm

  1. Define solve(i, currentSum).
  2. If i == n, return abs((totalSum - currentSum) - currentSum).
  3. Option 1: Include nums[i] in S1: solve(i + 1, currentSum + nums[i]).
  4. Option 2: Exclude nums[i] from S1: solve(i + 1, currentSum).
  5. Return min(Option 1, Option 2).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <cmath>
5#include <algorithm>
6
7using namespace std;
8
9class Solution {
10 int solve(int i, int currentSum, int totalSum, const vector<int>& nums) {
11 if (i == nums.size()) {
12 return abs((totalSum - currentSum) - currentSum);
13 }
14 int take = solve(i + 1, currentSum + nums[i], totalSum, nums);
15 int notTake = solve(i + 1, currentSum, totalSum, nums);
16 return min(take, notTake);
17 }
18public:
19 int minDifference(vector<int>& nums) {
20 int totalSum = accumulate(nums.begin(), nums.end(), 0);
21 return solve(0, 0, totalSum, nums);
22 }
23};
24
25int main() {
26 Solution sol;
27 vector<int> nums = {1, 6, 11, 5};
28 cout << "Min Diff: " << sol.minDifference(nums) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) recursion stack

2. 2D Subset Sum Tabulation

Intuition

Create a 2D boolean table dp[n + 1][target + 1] where target = totalSum / 2.

Algorithm

  1. Let totalSum = sum(nums) and target = totalSum / 2.
  2. Initialize dp[n + 1][target + 1] with false; dp[0][0] = true.
  3. Fill standard 0/1 knapsack:
  4. dp[i][s] = dp[i-1][s] || (s >= nums[i-1] ? dp[i-1][s - nums[i-1]] : false).
  5. Scan row n from target down to 0 for the first true value.
  6. Return totalSum - 2 * s.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4#include <cmath>
5
6using namespace std;
7
8class Solution {
9public:
10 int minDifference(vector<int>& nums) {
11 int n = nums.size();
12 int totalSum = accumulate(nums.begin(), nums.end(), 0);
13 int target = totalSum / 2;
14
15 vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
16 for (int i = 0; i <= n; ++i) dp[i][0] = true;
17
18 for (int i = 1; i <= n; ++i) {
19 for (int s = 1; s <= target; ++s) {
20 dp[i][s] = dp[i - 1][s];
21 if (s >= nums[i - 1]) {
22 dp[i][s] = dp[i][s] || dp[i - 1][s - nums[i - 1]];
23 }
24 }
25 }
26
27 for (int s = target; s >= 0; --s) {
28 if (dp[n][s]) {
29 return totalSum - 2 * s;
30 }
31 }
32
33 return 0;
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<int> nums = {1, 6, 11, 5};
40 cout << "Min Diff: " << sol.minDifference(nums) << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(n * totalSum)
  • Space complexity: O(n * totalSum)

3. Space-Optimized 1D Bitset / Array (O(totalSum) Space)

Intuition

Use a single 1D boolean array traversed in reverse from target down to num to avoid using elements more than once.

Algorithm

  1. Compute totalSum = sum(nums) and target = totalSum / 2.
  2. Initialize boolean array dp of size target + 1 with false; dp[0] = true.
  3. For each num in nums:
  4. For s from target down to num:
  5. dp[s] = dp[s] || dp[s - num].
  6. Find the largest s in [0, target] where dp[s] is true.
  7. Return totalSum - 2 * s.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <numeric>
4
5using namespace std;
6
7class Solution {
8public:
9 int minDifference(vector<int>& nums) {
10 int totalSum = accumulate(nums.begin(), nums.end(), 0);
11 int target = totalSum / 2;
12
13 vector<bool> dp(target + 1, false);
14 dp[0] = true;
15
16 for (int num : nums) {
17 for (int s = target; s >= num; --s) {
18 dp[s] = dp[s] || dp[s - num];
19 }
20 }
21
22 for (int s = target; s >= 0; --s) {
23 if (dp[s]) {
24 return totalSum - 2 * s;
25 }
26 }
27
28 return 0;
29 }
30};
31
32int main() {
33 Solution sol;
34 vector<int> nums = {1, 6, 11, 5};
35 cout << "Min Diff: " << sol.minDifference(nums) << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(n * totalSum)
  • Space complexity: O(totalSum)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Inclusion / ExclusionO(2^n)O(n)Exhaustive branching over subsets.Overlapping subsets
2.2D Subset Sum TabulationO(n * totalSum)O(n * totalSum)Build 2D boolean reachability matrix.Matrix allocation
3.1D Reverse Knapsack ArrayOptimalO(n * totalSum)O(totalSum)Single 1D boolean array traversed backwards.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Iterating forward in the 1D DP array, which converts 0/1 Knapsack to Unbounded Knapsack.

Pitfall 2:

Searching past totalSum / 2: Any subset sum > totalSum / 2 is symmetric to a subset sum < totalSum / 2.

Crucial Edge Cases to Validate:

  • Array of identical elements: If even length, min diff is 0; if odd length, min diff is nums[0].
  • Two elements: Returns abs(nums[0] - nums[1]).
  • Array summing to 0: Returns 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that this problem is NP-hard (subset sum partition) but admits a pseudo-polynomial time dynamic programming solution.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the inner loop in the 1D knapsack approach iterate from target DOWN to num (in reverse)?

Back to DSA Sheet