Partition Array Into Two Arrays to Minimize Sum Difference solution and explanation
Google
9 more videos on this problem
Meet in the Middle | 2035. Partition Array Into Two Arrays to Minimize Sum Difference | Day 022Aryan Mittal · 54:07 · 38K views
Partition Array Into Two Arrays to Minimize Sum Difference | Leetcode 2035Techdose · 24:15 · 21K views
Meet In The Middle Technique | Leetcode Partition Array Into Two Arrays to Minimize Sum DifferenceNot A Boring Developer · 31:47 · 18K views
Leetcode Weekly Contest 262, 2035 Partition Array Into Two Arrays to Minimize Sum Difference(Hard)Competitive Somya · 14:46 · 12K views
2035. Partition Array Into Two Arrays to Minimize Sum Difference (Leetcode Hard)Programming Live with Larry · 45:03 · 5K views
LeetCode 2035: Partition Array Into Two Arrays to Minimize Sum Difference (This video is in Hebrew!)cpp in pajamas · 24:50 · 140 views
leetcode 2035 Partition Array Into Two Arrays to Minimize Sum DifferenceClimbWithCode · 35:07 · 112 views
Leetcode : 2035 Partition Array Into Two Arrays to Minimize Sum DifferenceUnbound Coder · 24:56 · 111 views
Leetcode 2035. Partition Array Into Two Arrays to Minimize Sum DifferenceClimbWithCode · 38:02 · 36 views
LeetCode 2035: Partition Array Into Two Arrays to Minimize Sum DifferenceAlitaCode · 33:05 · 34 views
The problem
You are given an integer array nums of 2 * n integers. You need to partition nums into two arrays of length n to minimize the absolute difference of the sums of the arrays. To partition nums, put each element of nums into one of the two arrays.
Return the minimum possible absolute difference.
Example 1:
Input: nums = [3,9,7,3] Output: 2 Explanation: One optimal partition is: [3,9] and [7,3]. The absolute difference between the sums of the arrays is abs((3 + 9) - (7 + 3)) = 2.
Example 2:
Input: nums = [-36,36] Output: 72 Explanation: One optimal partition is: [-36] and [36]. The absolute difference between the sums of the arrays is abs((-36) - (36)) = 72.
Example 3:
Input: nums = [2,-1,0,4,-2,-9] Output: 0 Explanation: One optimal partition is: [2,4,-9] and [-1,0,-2]. The absolute difference between the sums of the arrays is abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0.
Constraints:
1 <= n <= 15nums.length == 2 * n-107 <= nums[i] <= 107
Approach overview
Problem Overview: You are given an array of 2n integers. Split it into two groups of size n so the absolute difference between their sums is minimized. The challenge is exploring combinations efficiently without enumerating all C(2n, n) possibilities.
Approach 1: Backtracking with Subset Sum / Meet-in-the-Middle (Time: O(n * 2^(n/2)), Space: O(2^(n/2)))
Brute forcing every partition is infeasible because the number of combinations grows exponentially. A better strategy splits the array into two halves and enumerates subset sums for each half using bitmask or backtracking. For the first half, store sums grouped by how many elements were chosen. Do the same for the second half. The total array sum is fixed, so you only need combinations that select exactly n elements across both halves.
For each subset sum from the first half, search the second-half sums that bring the total as close as possible to totalSum / 2. Sorting the second-half sums allows fast lookup using binary search. This technique is a classic meet-in-the-middle optimization: generate 2^(n/2) subsets instead of 2^n. The best candidate minimizes |totalSum - 2 * chosenSum|. The approach heavily relies on efficient subset enumeration and grouping by subset size.
Approach 2: Dynamic Programming with Subset Sum (Time: O(n * S), Space: O(S))
This method treats the problem as a balanced subset sum. The goal is to pick exactly n elements whose sum is as close as possible to totalSum / 2. Using dynamic programming, maintain states representing achievable sums with a given number of elements. Transition by either including or excluding each number.
The DP table tracks dp[count][sum], meaning whether a subset of count elements can produce a given sum. After processing all numbers, examine sums reachable with exactly n elements and pick the one closest to half of the total. This approach is conceptually simple but becomes expensive when the sum range is large, which is why meet-in-the-middle is typically preferred.
Recommended for interviews: The meet-in-the-middle subset enumeration is the expected solution for this problem. It demonstrates strong understanding of exponential optimization, array partitioning strategies, and efficient search with binary search. A plain subset DP shows the correct problem framing but struggles with large numeric ranges.
Approach 1: Approach 1: Backtracking with Subset Sum
In this approach, we use a backtracking method to generate all possible partitions of the array into two subarrays of equal size. We then calculate the sum of the elements in each subarray and find the minimum absolute difference between these sums.
Generate all possible combinations for dividing the array elements into two subarrays of size n, leveraging backtracking techniques. For each valid partition, compute the sum of both subarrays and determine the absolute difference. Continue this process while tracking the minimum absolute difference encountered.
from itertools import combinations
def minDifference(nums):
n = len(nums) // 2
total_sum = sum(nums)
min_diff = float('inf')
for combo in combinations(nums, n):
curr_sum = sum(combo)
other_sum = total_sum - curr_sum
min_diff = min(min_diff, abs(curr_sum - other_sum))
return min_diff
nums = [3, 9, 7, 3]
print("Minimum Difference:", minDifference(nums))import java.util.Arrays;
public class MinDiff {
static int totalSum;
public static void main(String[] args) {
int[] nums = {3, 9, 7, 3};
System.out.println("Minimum Difference: " + minDifference(nums));
}
public static int minDifference(int[] nums) {
totalSum = Arrays.stream(nums).sum();
return backtrack(nums, 0, 0, nums.length/2);
}
private static int backtrack(int[] nums, int start, int currSum, int cnt) {
if (cnt == 0) {
return Math.abs(currSum - (totalSum - currSum));
}
int minDiff = Integer.MAX_VALUE;
for (int i = start; i <= nums.length - cnt; i++) {
minDiff = Math.min(minDiff, backtrack(nums, i + 1, currSum + nums[i], cnt - 1));
}
return minDiff;
}
}#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
void backtrack(const std::vector<int>& nums, std::vector<bool>& used, int n, int idx, int cnt, int currSum, int& minDiff) {
static int totalSum;
if (cnt == n/2) {
int otherSum = totalSum - currSum;
minDiff = std::min(minDiff, std::abs(currSum - otherSum));
return;
}
if (idx >= n) return;
used[idx] = true;
backtrack(nums, used, n, idx + 1, cnt + 1, currSum + nums[idx], minDiff);
used[idx] = false;
backtrack(nums, used, n, idx + 1, cnt, currSum, minDiff);
}
int minDifference(std::vector<int>& nums) {
int n = nums.size();
int totalSum = std::accumulate(nums.begin(), nums.end(), 0);
int minDiff = INT_MAX;
std::vector<bool> used(n, false);
backtrack(nums, used, n, 0, 0, 0, minDiff);
return minDiff;
}
int main() {
std::vector<int> nums = {3, 9, 7, 3};
std::cout << "Minimum Difference: " << minDifference(nums) << std::endl;
return 0;
}function minDifference(nums) {
const n = nums.length / 2;
const totalSum = nums.reduce((a, b) => a + b, 0);
let minDiff = Infinity;
function backtrack(index, currSum, count) {
if (count === 0) {
const otherSum = totalSum - currSum;
minDiff = Math.min(minDiff, Math.abs(currSum - otherSum));
return;
}
if (index >= nums.length) return;
// Take the current element
backtrack(index + 1, currSum + nums[index], count - 1);
// Don't take the current element
backtrack(index + 1, currSum, count);
}
backtrack(0, 0, n);
return minDiff;
}
const nums = [3, 9, 7, 3];
console.log('Minimum Difference:', minDifference(nums));#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void findPartitions(int* nums, int n, int* minDiff, int start, int currentSum, int cnt) {
static int totalSum;
if (cnt == 0) {
int subsetSum = totalSum - currentSum;
int diff = abs((currentSum) - (subsetSum));
if (*minDiff > diff)
*minDiff = diff;
return;
}
for (int i = start; i <= n; ++i) {
findPartitions(nums, n, minDiff, i + 1, currentSum + nums[i], cnt - 1);
}
}
int minSumDiff(int* nums, int numsSize) {
int n = numsSize / 2;
int minDiff = INT_MAX;
int totalSum = 0;
for (int i = 0; i < numsSize; ++i) totalSum += nums[i];
findPartitions(nums, n, &minDiff, 0, 0, n);
return minDiff;
}
int main() {
int nums[] = {3, 9, 7, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("Minimum Difference: %d\n", minSumDiff(nums, numsSize));
return 0;
}using System;
using System.Linq;
class Program
{
static void Main()
{
int[] nums = {3, 9, 7, 3};
Console.WriteLine("Minimum Difference: " + MinDifference(nums));
}
static int MinDifference(int[] nums)
{
int n = nums.Length / 2;
int totalSum = nums.Sum();
int minDiff = int.MaxValue;
Explore(nums, new bool[nums.Length], 0, 0, 0, n, ref minDiff, totalSum);
return minDiff;
}
static void Explore(int[] nums, bool[] used, int index, int currSum, int count, int target, ref int minDiff, int totalSum)
{
if (count == target)
{
int otherSum = totalSum - currSum;
minDiff = Math.Min(minDiff, Math.Abs(currSum - otherSum));
return;
}
if (index >= nums.Length) return;
used[index] = true;
Explore(nums, used, index + 1, currSum + nums[index], count + 1, target, ref minDiff, totalSum);
used[index] = false;
Explore(nums, used, index + 1, currSum, count, target, ref minDiff, totalSum);
}
}Python's itertools.combinations method is used to generate all possible combinations of size n from the list. For each combination, their summation is calculated, and alongside the remaining elements, we note down their difference of summation to determine the minimum.
Time Complexity: O(n choose n/2), due to combinations generation
Space Complexity: O(n) for storing combinations.
Approach 2: Approach 2: Dynamic Programming and Subset Sum
This approach utilizes dynamic programming to solve the subset sum problem for optimization. It determines the possible sum values that can be achieved by selecting subsets from the input array. With a goal of minimizing the absolute difference of the two partitions, the best achievable partition is directly extracted from the possible sums identified by the DP array.
Divide the array into two. For each half, build an array of all possible subset sums. Use a combination of these to get the closest possible sum to half of the total. Used efficiently, the technique ensures the minimum difference.
def minDifference(nums):
total_sum = sum(nums)
n = len(nums)
target = total_sum // 2
dp = [0] * (target + 1)
for val in nums:
for j in range(target, val - 1, -1):
dp[j] = max(dp[j], dp[j - val] + val)
min_diff = float('inf')
for i in range(target + 1):
min_diff = min(min_diff, abs((total_sum - dp[i]) - dp[i]))
return min_diff
nums = [3, 9, 7, 3]
print("Minimum Difference:", minDifference(nums))import java.util.Arrays;
public class MinDiff {
public static void main(String[] args) {
int[] nums = {3, 9, 7, 3};
System.out.println("Minimum Difference: " + minDifference(nums));
}
public static int minDifference(int[] nums) {
int totalSum = Arrays.stream(nums).sum();
int n = nums.length;
int target = totalSum / 2;
int[] dp = new int[target + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int val : nums) {
for (int j = target; j >= val; --j) {
if (dp[j - val] != Integer.MAX_VALUE)
dp[j] = Math.min(dp[j], dp[j - val] + Math.abs(j + j - totalSum));
}
}
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i <= target; ++i)
if (dp[i] != Integer.MAX_VALUE)
minDiff = Math.min(minDiff, dp[i]);
return minDiff;
}
}#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
int minDifference(std::vector<int>& nums) {
int n = nums.size();
int totalSum = std::accumulate(nums.begin(), nums.end(), 0);
int target = totalSum / 2;
std::vector<int> dp(target + 1, INT_MAX);
dp[0] = 0;
for (int val : nums) {
for (int j = target; j >= val; --j) {
if (dp[j - val] != INT_MAX)
dp[j] = std::min(dp[j], dp[j - val] + std::abs(j + j - totalSum));
}
}
int minDiff = INT_MAX;
for (int i = 0; i <= target; ++i)
if (dp[i] != INT_MAX)
minDiff = std::min(minDiff, dp[i]);
return minDiff;
}
int main() {
std::vector<int> nums = {3, 9, 7, 3};
std::cout << "Minimum Difference: " << minDifference(nums) << std::endl;
return 0;
}function minDifference(nums) {
const totalSum = nums.reduce((a, b) => a + b, 0);
const n = nums.length;
const target = Math.floor(totalSum / 2);
const dp = new Array(target + 1).fill(0);
for (const val of nums) {
for (let j = target; j >= val; --j) {
dp[j] = Math.max(dp[j], dp[j - val] + val);
}
}
let minDiff = Infinity;
for (const val of dp) {
minDiff = Math.min(minDiff, Math.abs((totalSum - val) - val));
}
return minDiff;
}
const nums = [3, 9, 7, 3];
console.log('Minimum Difference:', minDifference(nums));#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
int min(int a, int b) {
return a < b ? a : b;
}
int abs(int a) {
return a >= 0 ? a : -a;
}
int minDifference(int* nums, int numsSize) {
int n = numsSize / 2;
int totalSum = 0;
for (int i = 0; i < numsSize; ++i) totalSum += nums[i];
int target = totalSum / 2;
int dp[target + 1];
for (int i = 0; i <= target; ++i) dp[i] = INT_MAX;
dp[0] = 0;
for (int i = 0; i < numsSize; ++i) {
for (int j = target; j >= nums[i]; --j) {
if (dp[j - nums[i]] != INT_MAX)
dp[j] = min(dp[j], dp[j - nums[i]] + abs(j + j - totalSum));
}
}
int minDiff = INT_MAX;
for (int i = 0; i <= target; ++i)
if (dp[i] != INT_MAX)
minDiff = min(minDiff, dp[i]);
return minDiff;
}
int main() {
int nums[] = {3, 9, 7, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("Minimum Difference: %d\n", minDifference(nums, numsSize));
return 0;
}using System;
using System.Linq;
class Program
{
static void Main()
{
int[] nums = {3, 9, 7, 3};
Console.WriteLine("Minimum Difference: " + MinDifference(nums));
}
static int MinDifference(int[] nums)
{
int totalSum = nums.Sum();
int n = nums.Length;
int target = totalSum / 2;
int[] dp = new int[target + 1];
foreach (int val in nums)
{
for (int j = target; j >= val; --j)
{
dp[j] = Math.Max(dp[j], dp[j - val] + val);
}
}
int minDiff = int.MaxValue;
foreach (int i in dp)
{
minDiff = Math.Min(minDiff, Math.Abs((totalSum - i) - i));
}
return minDiff;
}
}Python employs a classic dynamic programming approach to tackle the suggested problem. The function builds an array `dp` where it iteratively uses existing int elements to determine sums that lead to a minimum deviation above or below half of the total existing sum.
Time Complexity: O(n * sum) where sum is the target based on input. Space Complexity: O(sum).
Approach 3: Default Approach
func minimumDifference(nums []int) int {
n := len(nums) >> 1
f := make([][]int, n+1)
g := make([][]int, n+1)
for i := 0; i < (1 << n); i++ {
s, cnt := 0, 0
s1, cnt1 := 0, 0
for j := 0; j < n; j++ {
if (i & (1 << j)) != 0 {
s += nums[j]
cnt++
s1 += nums[n+j]
cnt1++
} else {
s -= nums[j]
s1 -= nums[n+j]
}
}
f[cnt] = append(f[cnt], s)
g[cnt1] = append(g[cnt1], s1)
}
for i := 0; i <= n; i++ {
sort.Ints(f[i])
sort.Ints(g[i])
}
ans := 1 << 30
for i := 0; i <= n; i++ {
for _, a := range f[i] {
left, right := 0, len(g[n-i])-1
b := -a
for left < right {
mid := (left + right) >> 1
if g[n-i][mid] >= b {
right = mid
} else {
left = mid + 1
}
}
ans = min(ans, abs(a+g[n-i][left]))
if left > 0 {
ans = min(ans, abs(a+g[n-i][left-1]))
}
}
}
return ans
}
func abs(x int) int {
if x > 0 {
return x
}
return -x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking with Subset Sum | Time Complexity: O(n choose n/2), due to combinations generation |
| Approach 2: Dynamic Programming and Subset Sum | Time Complexity: O(n * sum) where sum is the target based on input. Space Complexity: O(sum). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking / Meet-in-the-Middle Subset Sums | O(n * 2^(n/2)) | O(2^(n/2)) | Best practical solution when n ≤ 15 per half; typical interview and competitive programming approach |
| Dynamic Programming Subset Sum | O(n * S) | O(S) | Works when total sum range is small and memory allows DP over sums |
Frequently asked questions
Is Partition Array Into Two Arrays to Minimize Sum Difference easy or hard?
LeetCode classifies this problem as Hard with a low acceptance rate around 23%. It requires recognizing the meet-in-the-middle optimization and managing subset sums grouped by element count, which is more advanced than standard subset sum problems.
Partition Array Into Two Arrays to Minimize Sum Difference Python/Java solution
Most Python and Java solutions implement the meet-in-the-middle strategy. Generate subset sums for the first half grouped by element count, generate the same for the second half, sort the lists, and apply binary search to find sums that minimize |totalSum − 2 * chosenSum|.
How to solve Partition Array Into Two Arrays to Minimize Sum Difference in O(n)?
An O(n) solution is not possible because the problem requires exploring combinations of elements. The best practical complexity is O(n * 2^(n/2)) using a meet-in-the-middle technique that enumerates subset sums for each half and matches them using binary search.
What is the best approach for Partition Array Into Two Arrays to Minimize Sum Difference?
The most efficient approach is meet-in-the-middle with subset sums. Split the array into two halves, compute all subset sums for each half, and use binary search to combine them while ensuring exactly n elements are selected. This reduces complexity from O(2^n) to roughly O(n * 2^(n/2)), which is feasible for arrays up to 30 elements.
Is Partition Array Into Two Arrays to Minimize Sum Difference asked at Google/Amazon/Meta?
This problem represents a classic meet-in-the-middle subset partition pattern often seen in interviews at companies like Google, Amazon, and Meta. Variants of balanced partitioning and subset sum optimization appear frequently in senior-level algorithm interviews.
What data structure is used in Partition Array Into Two Arrays to Minimize Sum Difference?
The solution typically uses arrays or lists to store subset sums, grouped by subset size. Sorting these lists enables binary search to find the closest complementary sum. Some implementations also use ordered sets or maps to manage sums efficiently.
What is the time complexity of Partition Array Into Two Arrays to Minimize Sum Difference?
The optimal meet-in-the-middle solution runs in O(n * 2^(n/2)) time with O(2^(n/2)) space. It generates subset sums for each half of the array and then uses binary search to find the closest complementary sums. A dynamic programming subset sum approach can take O(n * S) time where S is the total sum range.