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
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
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:
- We need to find two subsets of the array whose sums are as close as possible.
- 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
- Calculate Total Sum: Compute the total sum of the array elements.
- 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.
- Determine Sets: Using the closest sum identified, determine the two subsets. The remaining elements form the second subset.
Code
Java
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]
}
}
Python
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)
wheren
is the number of elements in the array andsum
is the total sum of the array. - 🧺 Space complexity:
O(n * sum/2)
due to the DP table used.