2035. Partition Array Into Two Arrays to Minimize Sum Difference Hard

1/**
2 * [2035] Partition Array Into Two Arrays to Minimize Sum Difference
3 *
4 * 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.
5 * Return the minimum possible absolute difference.
6 *  
7 * Example 1:
8 * <img alt="example-1" src="https://assets.leetcode.com/uploads/2021/10/02/ex1.png" style="width: 240px; height: 106px;" />
9 * Input: nums = [3,9,7,3]
10 * Output: 2
11 * Explanation: One optimal partition is: [3,9] and [7,3].
12 * The absolute difference between the sums of the arrays is abs((3 + 9) - (7 + 3)) = 2.
13 * 
14 * Example 2:
15 * 
16 * Input: nums = [-36,36]
17 * Output: 72
18 * Explanation: One optimal partition is: [-36] and [36].
19 * The absolute difference between the sums of the arrays is abs((-36) - (36)) = 72.
20 * 
21 * Example 3:
22 * <img alt="example-3" src="https://assets.leetcode.com/uploads/2021/10/02/ex3.png" style="width: 316px; height: 106px;" />
23 * Input: nums = [2,-1,0,4,-2,-9]
24 * Output: 0
25 * Explanation: One optimal partition is: [2,4,-9] and [-1,0,-2].
26 * The absolute difference between the sums of the arrays is abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0.
27 * 
28 *  
29 * Constraints:
30 * 
31 * 	1 <= n <= 15
32 * 	nums.length == 2 * n
33 * 	-10^7 <= nums[i] <= 10^7
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference/
39// discuss: https://leetcode.com/problems/partition-array-into-two-arrays-to-minimize-sum-difference/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn minimum_difference(nums: Vec<i32>) -> i32 {
45        0
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_2035() {
57    }
58}
59