partition-array-into-two-arrays-to-minimize-sum-difference

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>nums</code> of <code>2 * n</code> integers. You need to partition <code>nums</code> into two arrays of length <code>n</code> to minimize the absolute difference of the sums of the arrays. To partition <code>nums</code>, put each element of <code>nums</code> into one of the two arrays.

Return the minimum possible absolute difference.

&nbsp;
Example 1:
<img alt="example-1" src="https://assets.leetcode.com/uploads/2021/10/02/ex1.png" style="width: 240px; height: 106px;" />
<pre>
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.
</pre>

Example 2:

<pre>
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.
</pre>

Example 3:
<img alt="example-3" src="https://assets.leetcode.com/uploads/2021/10/02/ex3.png" style="width: 316px; height: 106px;" />
<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 15</code></li>
	<li><code>nums.length == 2 * n</code></li>
	<li><code>-107 &lt;= nums[i] &lt;= 107</code></li>
</ul>

minimumDifference

Partition Array Into Two Arrays to Minimize Sum Difference

Partition Equal Subset Sum

partition-equal-subset-sum

分割等和子集

Split Array With Same Average

split-array-with-same-average

数组的均值分割

Tallest Billboard

tallest-billboard

最高的广告牌

Last Stone Weight II

last-stone-weight-ii

最后一块石头的重量 II

Fair Distribution of Cookies

fair-distribution-of-cookies

公平分发饼干

Closest Subsequence Sum

closest-subsequence-sum

最接近目标值的子序列和

Number of Ways to Split Array

number-of-ways-to-split-array

分割数组的方案数

Minimum Sum of Squared Difference

minimum-sum-of-squared-difference

最小差值平方和

Split With Minimum Sum

split-with-minimum-sum

最小和分割

Bit Manipulation

Array

Two Pointers

Binary Search

Dynamic Programming

Bitmask

Ordered Set

给你一个长度为 <code>2 * n</code>&nbsp;的整数数组。你需要将&nbsp;<code>nums</code>&nbsp;分成&nbsp;两个&nbsp;长度为&nbsp;<code>n</code>&nbsp;的数组，分别求出两个数组的和，并 最小化&nbsp;两个数组和之&nbsp;差的绝对值&nbsp;。<code>nums</code>&nbsp;中每个元素都需要放入两个数组之一。

请你返回&nbsp;最小&nbsp;的数组和之差。

&nbsp;

示例 1：

<img alt="example-1" src="https://assets.leetcode.com/uploads/2021/10/02/ex1.png" style="width: 240px; height: 106px;">

<pre>输入：nums = [3,9,7,3]
输出：2
解释：最优分组方案是分成 [3,9] 和 [7,3] 。
数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。
</pre>

示例 2：

<pre>输入：nums = [-36,36]
输出：72
解释：最优分组方案是分成 [-36] 和 [36] 。
数组和之差的绝对值为 abs((-36) - (36)) = 72 。
</pre>

示例 3：

<img alt="example-3" src="https://assets.leetcode.com/uploads/2021/10/02/ex3.png" style="width: 316px; height: 106px;">

<pre>输入：nums = [2,-1,0,4,-2,-9]
输出：0
解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。
数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 15</code></li>
	<li><code>nums.length == 2 * n</code></li>
	<li><code>-107 &lt;= nums[i] &lt;= 107</code></li>
</ul>