Skip to main content
Talentd

Partition Array Into Two Arrays to Minimize Sum Difference - Solution & Explanation

HardArrayTwo PointersBinary SearchDynamic Programming19 min readAsked at: Amazon, Microsoft, Samsung +6
Practice this problem

Problem Statement

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:

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:

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 <= 15
  • nums.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.

This C implementation employs a backtracking technique to explore all subsets of the array of size n. For each subset, it calculates the complement set and checks the absolute difference of their sums. By iterating over all possibilities, it ensures that the minimum absolute difference is achieved. The solution tracks this value through recursion.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n) due to recursive subset creation.
Space Complexity: O(n) because of the recursion call stack space.

Try this approach in the editor →

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.

The C code defines a dynamic programming approach for subset sum determination, aiming to achieve close sums to half the total sum. A bottom-up approach is used for filling up the dp array, and finally, the minimum difference is extracted from the dp results.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * sum), where sum is total of the array.
Space Complexity: O(sum).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Backtracking with Subset Sum

Time Complexity: O(2^n) due to recursive subset creation.
Space Complexity: O(n) because of the recursion call stack space.

Approach 2: Dynamic Programming and Subset Sum

Time Complexity: O(n * sum), where sum is total of the array.
Space Complexity: O(sum).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking / Meet-in-the-Middle Subset SumsO(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 SumO(n * S)O(S)Works when total sum range is small and memory allows DP over sums

Video Solution

Meet in the Middle | 2035. Partition Array Into Two Arrays to Minimize Sum Difference | Day 022 • Aryan Mittal • 38,472 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Partition Array Into Two Arrays to Minimize Sum Difference with our built-in code editor and test cases.

Practice on FleetCode
Previous

Closest Subsequence Sum

Next

Fair Distribution of Cookies