Problem

Given an array of positive integers, divide the array into two subsets such that the difference between the sum of the subsets is as small as possible.

Examples

Example 1

1
2
3

Input: [5, 10, 15, 20, 25]
Output: ({10, 25}, {5, 15, 20})
Explanation: The sets {10, 25} and {5, 15, 20} have a difference of 5, which is the smallest possible difference.

Example 2

1
2
3

Input: [1, 2, 3, 4, 5]
Output: ({1, 4, 5}, {2, 3})
Explanation: The sets {1, 4, 5} and {2, 3} have a difference of 1, which is the smallest possible difference.

Solution

Method 1 - Using DP

This problem can be solved using dynamic programming. The approach is inspired by the Subset Sum Problem problem:

  1. We need to find two subsets of the array whose sums are as close as possible.
  2. By finding all subset sums up to half of the total sum, we can figure out the sum closest to half of the total sum. This would help in minimizing the difference between the two subsets.

Approach

  1. Calculate Total Sum: Compute the total sum of the array elements.
  2. Dynamic Programming Subset Sum: Use dynamic programming to determine possible subset sums up to half of the total sum. This will help in identifying the closest possible sum to half of the total sum.
  3. Determine Sets: Using the closest sum identified, determine the two subsets. The remaining elements form the second subset.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

public class Solution {
    public static List<List<Integer>> findMinDiffSubsets(int[] nums) {
        int totalSum = Arrays.stream(nums).sum();
        int n = nums.length;

        // DP array to check possible subset sums up to totalSum/2
        boolean[][] dp = new boolean[n + 1][totalSum / 2 + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }

        // Filling DP table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= totalSum / 2; j++) {
                if (nums[i - 1] <= j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        // Find the maximum possible value close to totalSum/2
        int closestSum = 0;
        for (int j = totalSum / 2; j >= 0; j--) {
            if (dp[n][j]) {
                closestSum = j;
                break;
            }
        }

        // Determine the two subsets
        List<Integer> subset1 = new ArrayList<>();
        List<Integer> subset2 = new ArrayList<>();
        int w = closestSum;
        for (int i = n; i > 0; i--) {
            if (!dp[i - 1][w]) {
                subset1.add(nums[i - 1]);
                w -= nums[i - 1];
            } else {
                subset2.add(nums[i - 1]);
            }
        }
        
        return Arrays.asList(subset1, subset2);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {5, 10, 15, 20, 25};
        List<List<Integer>> subsets = sol.findMinDiffSubsets(nums);
        System.out.println(subsets.get(0));  // Output: [25, 10]
        System.out.println(subsets.get(1));  // Output: [20, 15, 5]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution:
    def find_min_diff_subsets(self, nums: List[int]) -> Tuple[List[int], List[int]]:
        total_sum = sum(nums)
        n = len(nums)
        
        # DP array to check possible subset sums up to total_sum//2
        dp = [[False] * (total_sum // 2 + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = True

        # Fill DP table
        for i in range(1, n + 1):
            for j in range(1, total_sum // 2 + 1):
                if nums[i - 1] <= j:
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
                else:
                    dp[i][j] = dp[i - 1][j]
        
        # Find the maximum possible value closest to total_sum//2
        closest_sum = 0
        for j in range(total_sum // 2, -1, -1):
            if dp[n][j]:
                closest_sum = j
                break
        
        # Determine the two subsets
        subset1 = []
        subset2 = []
        w = closest_sum
        for i in range(n, 0, -1):
            if not dp[i - 1][w]:
                subset1.append(nums[i - 1])
                w -= nums[i - 1]
            else:
                subset2.append(nums[i - 1])
        
        return subset1, subset2

# Example usage
sol = Solution()
nums = [5, 10, 15, 20, 25]
subset1, subset2 = sol.find_min_diff_subsets(nums)
print(subset1)  # Output: [25, 10]
print(subset2)  # Output: [20, 15, 5]

Complexity

  • ⏰ Time complexity: O(n * sum/2) where n is the number of elements in the array and sum is the total sum of the array.
  • 🧺 Space complexity: O(n * sum/2) due to the DP table used.